Matriz de incidencia

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${\displaystyle n\times m}$matriz B , donde n y m son el número de vértices y aristas respectivamente, de tal manera que

${\displaystyle B_{ij}={\begin{cases}1&{\text{si el vértice }}v_{i}{\text{ es incidente con la arista }}e_{j},\\0&{\text{en otro caso.}}\end{cases}}}$

Por ejemplo, la matriz de incidencia del grafo no dirigido que se muestra a la derecha es una matriz que consta de 4 filas (que corresponden a los cuatro vértices, 1–4) y 4 columnas (que corresponden a las cuatro aristas,${\ Displaystyle e_ {1}, e_ {2}, e_ {3}, e_ {4}}$):

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${\displaystyle n\times m}$matriz B donde n y m son el número de vértices y aristas respectivamente, de tal manera que

${\displaystyle B_{ij}={\begin{cases}{-1}&{\text{si la arista }}e_{j}{\text{ sale del vértice }}v_{i},\\{\phantom {-}}1&{\text{si la arista }}e_{j}{\text{ entra en el vértice }}v_{i},\\{\phantom {-}}0&{\text{en otro caso.}}\end{cases}}}$

(Muchos autores utilizan la convención de signos opuesta).

La matriz de incidencia orientada de un grafo no dirigido es la matriz de incidencia, en el sentido de los 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 salvo la negación de cualquiera de las columnas, ya que negar las entradas de una columna equivale 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 de líneas L ( G ) mediante 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 grafo de líneas de G , B ( G ) es la matriz de incidencia, e I _m es la matriz identidad de dimensión m .

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

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

El espacio de ciclos integrales de un grafo es igual al espacio nulo de su matriz de incidencia orientada, vista como una matriz sobre los números enteros , reales o complejos. El espacio de ciclos binarios 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 de líneas 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 aristas múltiples . La columna de una matriz de incidencia orientada que corresponde a un bucle es toda cero, a menos que el grafo sea con 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 grafo ponderado se puede representar utilizando el peso de la arista en lugar de un 1. Por ejemplo, la matriz de incidencia del grafo de la derecha es:

Dado que 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. En cambio, un hipergrafo puede tener múltiples vértices asignados a una misma arista; por lo tanto, una matriz general de enteros no negativos describe un hipergrafo.

Un ejemplo importante es la 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 una unidad menor que la dimensión del espacio completo (hiperplanos); o, de forma 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 una unidad 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 los diseños de bloques. Por ejemplo, se puede usar para demostrar la desigualdad de Fisher , un teorema fundamental de los 2-diseños incompletos balanceados (BIBD), que establece que el número de bloques es al menos igual al número de puntos. ^{[ 2 ]} Considerando los bloques como un sistema de conjuntos, el permanente de la matriz de incidencia es el número de sistemas de representantes distintos (SDR).