Matriz de incidencia de un grafo y su homología

Muchas veces cuando se da un curso de Teoría de Grafos se introduce el concepto de matriz de incidencia, una matriz cuyas filas representan las aristas del grafo y cuyas columnas representan los vértices, de tal modo que la posición $(i,j)$ de la matriz es un $1$ si la arista $i$ es incidente a vértice $j$, y un $0$ si no lo es. Existe una generalización más o menos natural de esta matriz para grafos dirigidos: la matriz de incidencia dirigida, que en la posición $(i,j)$ tiene un $1$ si la arista $i$ "sale" del vértice $j$, un $-1$ si la arista $i$ "entra" al vértice $j$, y un $0$ si la arista $i$ no es incidente a vértice $j$.

Por ejemplo, pongamos que tenemos el grafo $G$

La matriz de incidencia dirigida de este grafo es
$$A = \begin{pmatrix} 1 & 0 & 0 & -1 \\
1 & -1 & 0 & 0\\
0 & 1 & -1 & 0\\
0 & 0 & -1 & 1\end{pmatrix}$$

donde la fila $i$ representa la arista $\varepsilon_i$ y la columna $j$ representa el vértice $e_j$. Si alguien no encuentra esta matriz dirigida como una generalización de la no dirigida, puede pensar que la primera se obtiene asignando direcciones cualesquiera a las aristas y cocientando sus coeficientes módulo $2$ (en $\mathbb{Z}/(2)$, $1$ y $-1$ representan el mismo elemento).

La matriz de incidencia dirigida, tal y como se enseña en los cursos de Matemática Discreta, tiene propiedades sorprendentes. Por ejemplo, se puede demostrar que si $G$ es un grafo conexo de $n$ vértices, entonces su matriz de incidencia tiene rango $n-1$, o que si un conjunto de aristas (filas) es linealmente independiente, entonces estas aristas no contienen ningún ciclo. Notemos que estas afirmaciones no dependen de las orientaciones de las aristas: dar la vuelta a una de las flechas equivale a multiplicar por $-1$ la fila correspondiente en la matriz de incidencia, lo cual no afecta a las relaciones de dependencia lineal. También son independientes del etiquetado del grafo porque intercambiar los nombres de dos vértices o dos artistas equivale, respectivamente, a permutar las correspondientes columnas o filas de la matriz. El caso de grafos no dirigidos es un poco distinto; la matriz de incidencia sin dirigir no tiene tan buenas propiedades. Por ejemplo, si el grafo es conexo, entonces la matriz de incidencia dirigida tiene rango $n-1$ o $n$, dependiendo de si $G$ es bipartito o no. Además, un conjunto de aristas (filas) es linealmente independiente si, y sólo si, estas aristas no contienen ningún ciclo o bien contienen un único ciclo pero de longitud impar.

¿Cómo es posible que tengamos estos resultados sobre dependencia lineal con una matriz que hemos construido sólo para escribir el grafo en forma de matriz? La respuesta nos la da la topología algebraica. Sea $G$ un grafo con vértices $e_1, ..., e_n$ y aristas $\varepsilon_1, ..., \varepsilon_m$. Vamos a calcular la homología simplicial del grafo, por ejemplo, con coeficientes reales, donde los vértices son $0$-símplices y las aristas son $1$-símplices. Para ello elegimos orientaciones para las aristas y consideramos la sucesión de espacios vectoriales y aplicaciones lineales

$$0 \stackrel{\iota}{\rightarrow} \mathbb{R}^m \stackrel{f}{\rightarrow} \mathbb{R}^n \stackrel{\pi}{\rightarrow} 0$$

donde $\iota$ es la inclusión, $\pi$ es la proyección de todo $\mathbb{R}^n$ al espacio $\{0\}$ y $f$ es la aplicación lineal que manda el elemento $\varepsilon_i$ de la base a $e_k-e_\ell$ si la arista $\varepsilon_i$ va del vértice $e_k$ al vértice $e_\ell$. Ahora tomamos los grupos (espacios vectoriales) de homología considerando los cocientes entre imágenes y núcleos. El primer grupo, $H^0$, es el cociente entre el núcleo de $\pi$, que es todo $\mathbb{R}^n$, y la imagen de $f$:

$$H^0 = \mathbb{R}^n/\text{Im }f$$

El segundo grupo, $H^1$, es el cociente entre el núcleo de $f$ y la imagen de $\iota$, que es $\{0\}$, luego

$$H^1 = \ker f/0 = \ker f$$
y el homomorfismo del borde, $\partial$, manda la clase de $\varepsilon_i$ a la clase de $e_k-e_\ell$.
$$0 \rightarrow H^1 \stackrel{\partial}{\rightarrow} H^0 \rightarrow 0$$

¿Cuál es la matriz de $f$ en las bases $\varepsilon_1, ..., \varepsilon_m$ y $e_1, ..., e_n$? Es la traspuesta de la matriz de incidencia dirigida del grafo $G$, una matriz de tamaño $n \times m$. Recordemos ahora que en la homología simplicial la dimensión de $H^0$ es el número de componentes conexas y la dimensión de $H^1$ es el número de ciclos (agujeros) del espacio topológico en cuestión. Pongamos que el grafo $G$ es conexo. Entonces la dimensión de $H^0$ debe ser $1$, y como $H^0 = \mathbb{R}^n/\text{Im }f$, la dimensión de $\text{Im }f$ debe ser, exactamente, $n-1$, el rango de la matriz asociada a $f$. Supongamos que tomamos un conjunto de aristas del grafo. Sin pérdida de generalidad podemos suponer que son todas las aristas del grafo, porque de no ser así podríamos construir la homología del subgrafo asociado a esas aristas. Pongamos que estas aristas contienen $d$ ciclos. Entonces la dimensión de $H^1$ debe ser $d$, y como $H^1 = \ker f$, la dimensión de $\ker f$ debe ser $d$. Si $d = 0$, entonces la aplicación $f$ es inyectiva, por lo que las aristas son linealmente independientes, pero si $d > 0$, entonces $f$ no es inyectiva y las aristas son linealmente dependientes.

Si queremos hacer algo parecido para el grafo sin dirigir, podemos considerar la homología simplicial del grafo pero, en lugar de tomar los coeficientes en $\mathbb{R}$, los tomamos en el cuerpo $\mathbb{Z}/(2)$, en el que $1$ y $-1$ son el mismo número. De esta manera nos quitamos de en medio las excepciones del tipo "un único ciclo de longitud impar" o "rango $n$ si $G$ es bipartito" (un grafo es bipartito si, y sólo si, no contiene ciclos de longitud impar). Esta manera de demostrar las propiedades de la matriz de incidencia es, sin duda, mucho más cómoda que la manera habitual que se emplea en los cursos de Matemática Discreta: razonamientos inductivos que deben distinguir muchos casos y hacer muchas operaciones con matrices. Espero que sea de utilidad.