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 
miniatura|256x256px| 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 , onde n e m son os números de vértices e arestas respectivamente, de tal forma que



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 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1 = 
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  onde n e m son o número de vértices e arestas respectivamente, de xeito que



(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:



onde A(L(G)) é a matriz de adxacencia do grafo liña de G, B(G) é a matriz de incidencia e Im é 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



 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 
miniatura| 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 = 

 Estruturas de incidencia 
A matriz de incidencia dunha estrutura de incidencia C é unha matriz  B  (ou a súa transposta), onde p e q son o número de puntos e liñas respectivamente, de tal forma que  se o punto pi e a liña Lj 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.
 Notas 


 Véxase tamén 

 Bibliografía 

 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 


Categoría:Matrices
Categoría:Combinatoria
Categoría:Teoría de grafos
Categoría:Wikipedia:Páxinas con traducións non revisadas