Matriz de incidencia

En matemáticas, unha matriz de incidencia é unha matriz lóxica que mostra a relación entre dúas clases de obxectos, normalmente chamada relación de incidencia. Se a primeira clase é X e a segunda é Y, a matriz ten unha fila para cada elemento de X e unha columna para cada asignación de X a Y.

A entrada na fila x e columna y é 1 se o vértice x forma parte (denominado incidente neste contexto) do mapa que corresponde a y, e 0 se non o é.

Hai algunha variante; ver a continuación.

Teoría de grafos

A matriz de incidencia é unha representación gráfica común na teoría de grafos. É diferente a unha matriz de adxacencia, que codifica a relación de pares vértice-vértice.

Grafos non orientados e orientados

Un grafo non orientado.

Na teoría de grafos un grafo non orientado ten dous tipos de matrices de incidencia: non orientadas e orientadas.

A matriz de incidencia non orientada (ou simplemente matriz de incidencia) dun grafo non orientado é a matriz B $n\times m$, onde n e m son os números de vértices e arestas respectivamente, de tal forma que

$B_{ij}=\left\{{\begin{array}{rl}\,1&{\text{se o vértice }}v_{i}{\text{ é incidente con aresta }}e_{j},\\0&{\text{noutro caso.}}\end{array}}\right.$

Por exemplo, a matriz de incidencia do grafo non orientado que se mostra á dereita é unha matriz formada por 4 filas (correspondentes aos catro vértices, 1-4) e 4 columnas (correspondentes ás catro arestas, $e_{1},e_{2},e_{3},e_{4}$):

e 1 e 2 e 3 e 4 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1

=

${\begin{bmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{bmatrix}}.$

Se observamos a matriz de incidencia, vemos que a suma de cada columna é igual a 2. Isto débese a que cada aresta ten un vértice ligado a cada extremo.

A matriz de incidencia dun grafo orientado é a matriz B $n\times m$ onde n e m son o número de vértices e arestas respectivamente, de xeito que

$B_{ij}=\left\{{\begin{array}{rl}{-1}&{\text{se a aresta }}e_{j}{\text{ sae do vértice }}v_{i},\\{\phantom {-}}1&{\text{se a aresta }}e_{j}{\text{ entra no vértice }}v_{i},\\{\phantom {-}}0&{\text{noutro caso.}}\end{array}}\right.$

(Moitos autores usan a convención de signo oposto).

A matriz de incidencia non orientada dun grafo G está relacionada coa matriz de adxacencia da súa grafo liña L(G) polo seguinte teorema:

$A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}.$

onde A(L(G)) é a matriz de adxacencia do grafo liña de G, B(G) é a matriz de incidencia e I_m é a matriz identidade da dimensión m.

O laplaciano discreto (ou matriz de Kirchhoff) obtense a partir da matriz de incidencia orientada B(G) mediante a fórmula

$B(G)B(G)^{\textsf {T}}.$

Multigrafos

As definicións de matriz de incidencia aplícanse a grafos con bucles e arestas múltiples. A columna dunha matriz de incidencia orientada que corresponde a un bucle é toda cero, a non ser que o grafo estea con signo e o bucle sexa negativo; entón a columna é toda cero agás ±2 na fila do seu vértice incidente.

Grafos ponderados

Un grafo ponderado non orientado

Un grafo ponderado pódese representar usando o peso da aresta en lugar de 1. Por exemplo, a matriz de incidencia do grafo da dereita é:

e 1 e 2 e 3 e 4 1 2 1 5 0 2 2 0 0 0 3 0 1 0 6 4 0 0 5 6

=

${\begin{bmatrix}2&1&5&0\\2&0&0&0\\0&1&0&6\\0&0&5&6\\\end{bmatrix}}.$

Estruturas de incidencia

A matriz de incidencia dunha estrutura de incidencia C é unha matriz B p × q (ou a súa transposta), onde p e q son o número de puntos e liñas respectivamente, de tal forma que B_i,j = 1 se o punto p_i e a liña L_j son incidentes e 0 en caso contrario.

Neste caso, a matriz de incidencia tamén é unha matriz de biadjacencia do grafo de Levi da estrutura. Como hai un hipergrafo para cada grafo de Levi, e viceversa, a matriz de incidencia dunha estrutura de incidencia describe un hipergrafo.

Xeometrías finitas

Un exemplo importante é unha xeometría finita. Por exemplo, nun plano finito, X é o conxunto de puntos e Y é o conxunto de liñas.

Nunha xeometría finita de dimensión superior, X podería ser o conxunto de puntos e Y podería ser o conxunto de subespazos de dimensión un menos que a dimensión de todo o espazo (hiperplanos); ou, de xeito máis xeral, X podería ser o conxunto de todos os subespazos dunha dimensión d e Y o conxunto de todos os subespazos doutra dimensión e, con "incidencia" definida como "estar contido en".

Polítopos

De xeito similar, a relación entre celas cuxas dimensións difiren nun polítopo, pódese representar mediante unha matriz de incidencia.

Véxase tamén

Bibliografía

• Diestel, Reinhard (2005). Graph Theory. Graduate Texts in Mathematics 173 (3rd ed.). Springer-Verlag. ISBN 3-540-26183-4. 
• Jonathan L Gross, Jay Yellen, Graph Theory and its applications, second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)

Outros artigos

• Relación binaria
• Matriz lóxica
• Camiño (teoría de grafos)

Ligazóns externas

• Weisstein, Eric W. "Incidence matrix". MathWorld.