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 la segunda es Y , la matriz tiene una fila por cada elemento de X y una columna por cada elemento de Y. La entrada en la fila x y la columna y es 1 si x e y están relacionados (llamado incidente en este contexto) y 0 si no lo están. Hay variaciones; vea abajo.
La matriz de incidencia es una representación gráfica común en la teoría de grafos . Es diferente a una matriz de adyacencia , que codifica la relación de pares vértice-vértice.
En teoría de grafos, un grafo no dirigido tiene dos tipos de matrices de incidencia: no orientadas y orientadas.
La matriz de incidencia no orientada (o simplemente matriz de incidencia ) de un gráfico no dirigido es una matriz B , donde n y m son los números de vértices y aristas respectivamente, tal que
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 las cuatro aristas ):
Si miramos la matriz de incidencia, vemos que la suma de cada columna es igual a 2. Esto se debe a que cada arista tiene un vértice conectado a cada extremo.
La matriz de incidencia de un gráfico dirigido es una matriz B donde n y m son el número de vértices y aristas respectivamente, tal que
(Muchos autores utilizan la convención de signos opuesta).
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 del borde e , hay un 1 en la fila correspondiente a un vértice de e y un −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 una arista.
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 ) mediante el siguiente teorema:
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 identidad de dimensión m .
El laplaciano discreto (o matriz de Kirchhoff) se obtiene a partir de la matriz de incidencia orientada B ( G ) mediante la fórmula
El espacio del ciclo integral de un gráfico es igual al espacio nulo de su matriz de incidencia orientada, vista como una matriz sobre los números enteros o reales o complejos . El espacio del ciclo binario es el espacio nulo de su matriz de incidencia orientada o no orientada, vista como una matriz sobre el campo de dos elementos .
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 una arista positiva tiene un 1 en la fila correspondiente a un punto final y un −1 en la fila correspondiente al otro punto final, como una arista en un gráfico ordinario (sin signo). La columna de un borde negativo tiene un 1 o un −1 en ambas filas. Las propiedades del gráfico lineal y de la matriz de Kirchhoff se generalizan a gráficos con signo.
Las definiciones de matriz de incidencia se aplican a gráficos con bucles y múltiples aristas . La columna de una matriz de incidencia orientada que corresponde a un bucle es toda cero, a menos que el gráfico tenga signo y el bucle sea negativo; entonces la columna es toda cero excepto ±2 en la fila de su vértice incidente.
Un gráfico ponderado se puede representar usando el peso del borde en lugar de 1. Por ejemplo, la matriz de incidencia del gráfico de la derecha es:
Debido a que las aristas 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 hipergrafo puede tener varios vértices asignados a un borde; por tanto, una matriz general de números enteros no negativos describe un hipergrafo.
La matriz de incidencia de una estructura de incidencia C es una matriz B p × q (o su transpuesta), donde p y q son el número de puntos y líneas respectivamente, tal 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 biadyacencia 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.
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 rectas. 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 menor 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.
De manera similar, la relación entre celdas cuyas dimensiones difieren en uno en un politopo se puede representar mediante una matriz de incidencia. [1]
Otro ejemplo es un diseño de bloques . 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, se puede utilizar para demostrar la desigualdad de Fisher , un teorema fundamental de los diseños 2 incompletos equilibrados (BIBD), de que el número de bloques es al menos el número de puntos. [2] Considerando los bloques como un sistema de conjuntos, la permanente de la matriz de incidencia es el número de sistemas de distintos representantes (SDR).
