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 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 e y están relacionadas (llamadas incidentes en este contexto) y 0 si no lo están. Hay variaciones; vea a continuación.
La matriz de incidencia es una representación gráfica común en la teoría de grafos . Es diferente de una matriz de adyacencia , que codifica la relación entre pares de vértices.
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 grafo no dirigido es una matriz B , donde n y m son los números de vértices y aristas respectivamente, tales 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 los cuatro bordes, ):
Si observamos 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 grafo dirigido es una matriz B donde n y m son el número de vértices y aristas respectivamente, tales que
(Muchos autores utilizan la convención de signos opuestos).
La matriz de incidencia orientada de un grafo no dirigido es la matriz de incidencia, en el sentido de grafos dirigidos, de cualquier orientación del grafo. Es decir, en la columna de la arista 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 única 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 grafo G está relacionada con la matriz de adyacencia de su grafo lineal L ( G ) por 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 y Im 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 cíclico integral de un grafo 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 cíclico binario es el espacio nulo de su matriz de incidencia orientada o no orientada, vista como una matriz sobre el cuerpo de dos elementos .
La matriz de incidencia de un grafo con signo es una generalización de la matriz de incidencia orientada. Es la matriz de incidencia de cualquier grafo bidireccional que orienta el grafo con signo dado. La columna de una arista positiva tiene un 1 en la fila correspondiente a un extremo y un −1 en la fila correspondiente al otro extremo, al igual que una arista en un grafo ordinario (sin signo). La columna de una arista negativa tiene un 1 o un −1 en ambas filas. Las propiedades del grafo lineal y de la matriz de Kirchhoff se generalizan a los grafos con signo.
Las definiciones de matriz de incidencia se aplican a grafos 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 grafo tenga signo y el bucle sea negativo; en ese caso, la columna es toda cero, excepto ±2 en la fila de su vértice incidente.
Un gráfico ponderado se puede representar utilizando el peso del borde en lugar de un 1. Por ejemplo, la matriz de incidencia del gráfico de la derecha es:
Como las aristas de los grafos ordinarios solo pueden tener dos vértices (uno en cada extremo), la columna de una matriz de incidencia para grafos solo puede tener dos entradas distintas de cero. Por el contrario, un hipergrafo puede tener múltiples vértices asignados a una arista; por lo 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 p × q B (o su transpuesta), donde p y q son el número de puntos y líneas respectivamente, tales 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 biyacencia del grafo de Levi de la estructura. Como hay un hipergrafo para cada grafo de Levi, y viceversa , la matriz de incidencia de una estructura de incidencia describe un hipergrafo.
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 mayor dimensión, 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, de manera más general, 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, puede representarse 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 balanceados (BIBDs), 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 representantes distintos (SDRs).
