Matriz de incidencia - Incidence matrix

En matemáticas , una matriz de incidencia es una matriz lógica que muestra la relación entre dos clases de objetos, generalmente llamada relación de incidencia . Si la primera clase es X y el segundo es Y , la matriz tiene una fila para cada elemento de X y una columna para cada elemento de Y . La entrada en la fila x y la columna y es 1 si x y y están relacionados (llamado incidente en este contexto) y 0 si no lo son. Hay variaciones; vea abajo.

Teoría de grafos

La matriz de incidencia es una representación gráfica común en la teoría de grafos . Es diferente de la matriz de adyacencia que codifica la relación de pares vértice-vértice.

Gráficos dirigidos y no dirigidos

En teoría de grafos, un grafo no dirigido tiene dos tipos de matrices de incidencia: no orientado y orientado.

La matriz de incidencia no orientada (o simplemente incidencia matriz ) de un grafo no dirigido es una matriz B , en donde n y m son los números de vértices y bordes , respectivamente, de manera que si el vértice y el borde son incidente y 0 en caso contrario. ${\ Displaystyle n \ times m}$ ${\ Displaystyle B_ {ij} = 1}$${\ Displaystyle v_ {i}}$${\ Displaystyle e_ {j}}$

Por ejemplo, la matriz de incidencia del gráfico no dirigido que se muestra a la derecha es una matriz que consta de 4 filas (correspondientes a los cuatro vértices, 1-4) y 4 columnas (correspondientes a los cuatro bordes ): ${\ Displaystyle 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

=

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

Si miramos la matriz de incidencia, vemos que la suma de cada columna es igual a 2. Esto se debe a que cada borde tiene un vértice conectado a cada extremo.

La matriz de incidencia de un grafo dirigido es una matriz B en donde n y m son el número de vértices y aristas respectivamente, tales que si el borde de vértice hojas , 1 si entra vértice y 0 en caso contrario (muchos autores utilizan la convención de signo contrario). ${\ Displaystyle n \ times m}$${\ Displaystyle B_ {ij} = - 1}$${\ Displaystyle e_ {j}}$${\ Displaystyle v_ {i}}$${\ Displaystyle v_ {i}}$

La matriz de incidencia orientada de un gráfico no dirigido es la matriz de incidencia, en el sentido de gráficos dirigidos, de cualquier orientación del gráfico. Es decir, en la columna de la arista e , hay un 1 en la fila correspondiente a un vértice de e y uno -1 en la fila correspondiente al otro vértice de e , y todas las demás filas tienen 0. La matriz de incidencia orientada es único hasta la negación de cualquiera de las columnas, ya que negar las entradas de una columna corresponde a invertir la orientación de un borde.

La matriz de incidencia no orientada de un gráfico G está relacionada con la matriz de adyacencia de su gráfico lineal L ( G ) por el siguiente teorema:

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

donde A ( L ( G )) es la matriz de adyacencia del gráfico lineal de G , B ( G ) es la matriz de incidencia e I _m es la matriz de identidad de dimensión m .

La laplaciana discreta (o matriz de Kirchhoff) se obtiene de la matriz de incidencia orientada B ( G ) mediante la fórmula

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

El espacio del ciclo integral de una gráfica es igual al espacio nulo de su matriz de incidencia orientada, visto como una matriz sobre los números enteros o reales o complejos . El espacio de ciclo binario es el espacio nulo de su matriz de incidencia orientada o no orientada, visto como una matriz sobre el campo de dos elementos .

Gráficos firmados y bidireccionales

La matriz de incidencia de un gráfico con signo es una generalización de la matriz de incidencia orientada. Es la matriz de incidencia de cualquier gráfico bidireccional que orienta el gráfico con signo dado. La columna de un borde positivo tiene un 1 en la fila correspondiente a un punto final y un -1 en la fila correspondiente al otro extremo, al igual que un borde en un gráfico ordinario (sin signo). La columna de un borde negativo tiene un 1 o un -1 en ambas filas. Las propiedades de la gráfica lineal y la matriz de Kirchhoff se generalizan a gráficas con signo.

Multigraphs

Las definiciones de matriz de incidencia se aplican a gráficos con bucles y aristas múltiples . La columna de una matriz de incidencia orientada que corresponde a un bucle es cero, a menos que la gráfica esté firmada y el bucle sea negativo; entonces toda la columna es cero excepto ± 2 en la fila de su vértice incidente.

Gráficos ponderados

Un gráfico ponderado se puede representar usando el peso del borde en lugar de un 1. Por ejemplo, la matriz de incidencia del gráfico de la derecha es:

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

=

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

Hipergrafos

Debido a que los bordes de los gráficos ordinarios solo pueden tener dos vértices (uno en cada extremo), la columna de una matriz de incidencia para gráficos solo puede tener dos entradas distintas de cero. Por el contrario, un hipergráfico puede tener varios vértices asignados a un borde; por tanto, una matriz general de números enteros no negativos describe un hipergráfico.

Estructuras de incidencia

La matriz de incidencia de una estructura de incidencia C es un p × q matriz B (o su transpuesta), donde p y q son el número de puntos y líneas , respectivamente, de manera que B _{i , j} = 1 si el punto p _i y la línea L _j son incidentes y 0 en caso contrario. En este caso, la matriz de incidencia es también una matriz de biadjacencia del gráfico de Levi de la estructura. Como hay un hipergráfico para cada gráfico de Levi, y viceversa , la matriz de incidencia de una estructura de incidencia describe un hipergráfico.

Geometrías finitas

Un ejemplo importante es una geometría finita . Por ejemplo, en un plano finito, X es el conjunto de puntos e Y es el conjunto de líneas. En una geometría finita de dimensión superior, X podría ser el conjunto de puntos e Y podría ser el conjunto de subespacios de dimensión uno menos que la dimensión de todo el espacio (hiperplanos); o, más generalmente, X podría ser el conjunto de todos los subespacios de una dimensión d e Y el conjunto de todos los subespacios de otra dimensión e , con incidencia definida como contención.

Politopos

De manera similar, la relación entre celdas cuyas dimensiones difieren en uno en un politopo, se puede representar mediante una matriz de incidencia.

Diseños de bloques

Otro ejemplo es un diseño de bloque . Aquí X es un conjunto finito de "puntos" e Y es una clase de subconjuntos de X , llamados "bloques", sujetos a reglas que dependen del tipo de diseño. La matriz de incidencia es una herramienta importante en la teoría de diseños de bloques. Por ejemplo, puede usarse para probar la desigualdad de Fisher , un teorema fundamental de los 2 diseños incompletos balanceados (BIBD), que el número de bloques es al menos el número de puntos. Considerando los bloques como un sistema de conjuntos, el permanente de la matriz de incidencia es el número de sistemas de representantes distintos (DEG).

Referencias

Otras lecturas

• Diestel, Reinhard (2005), Teoría de grafos , Textos de posgrado en matemáticas , 173 (3.a ed.), Springer-Verlag, ISBN 3-540-26183-4
• Jonathan L Gross, Jay Yellen, Teoría de grafos y sus aplicaciones , segunda edición, 2006 (p 97, Matrices de incidencia para gráficos no dirigidos; p 98, matrices de incidencia para dígrafos)

enlaces externos

• Weisstein, Eric W. "Matriz de incidencia" . MathWorld .