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