Teorema de Kirchhoff. Encontrar el número de árboles de expansión

Problema: Se da un grafo no dirigido conexo (con posibles aristas múltiples) representado con una matriz de adyacencia. Encontrar el número de árboles de expansión distintos de este grafo.

La siguiente fórmula la demostró Kirchhoff en 1847.

Teorema de Kirchhoff de la matriz de árboles

Sea $A$ la matriz de adyacencia del grafo: $A_{u,v}$ es el número de aristas entre $u$ y $v$. Sea $D$ la matriz de grados del grafo: una matriz diagonal con $D_{u,u}$ igual al grado del vértice $u$ (incluyendo aristas múltiples y bucles: aristas que conectan el vértice $u$ consigo mismo).

La matriz laplaciana del grafo se define como $L = D - A$. Según el teorema de Kirchhoff, todos los cofactores de esta matriz son iguales entre sí, y son iguales al número de árboles de expansión del grafo. El cofactor $(i,j)$ de una matriz es el producto de $(-1)^{i + j}$ por el determinante de la matriz que se obtiene al quitar la fila $i$ y la columna $j$. Así, se puede, por ejemplo, borrar la última fila y la última columna de la matriz $L$, y el valor absoluto del determinante de la matriz resultante dará el número de árboles de expansión.

El determinante de la matriz se puede encontrar en $O(N^3)$ usando el método de Gauss.

La demostración de este teorema es bastante difícil y no se presenta acá; para un esquema de la demostración y variaciones del teorema para grafos sin aristas múltiples y para grafos dirigidos, ver Wikipedia .

Relación con las leyes de Kirchhoff para circuitos

El teorema de Kirchhoff de la matriz de árboles y las leyes de Kirchhoff para circuitos eléctricos están relacionados de una forma bella. Es posible mostrar (usando la ley de Ohm y la primera ley de Kirchhoff) que la resistencia $R_{ij}$ entre dos puntos del circuito $i$ y $j$ es

$$R_{ij} = \frac{ \left| L^{(i,j)} \right| }{ | L^j | }.$$

Acá la matriz $L$ se obtiene de la matriz de inversas de resistencias $A$ ($A_{i,j}$ es la inversa de la resistencia del conductor entre los puntos $i$ y $j$) usando el procedimiento descrito en el teorema de Kirchhoff de la matriz de árboles. $T^j$ es la matriz con la fila y la columna $j$ quitadas, $T^{(i,j)}$ es la matriz con dos filas y dos columnas $i$ y $j$ quitadas.

El teorema de Kirchhoff le da a esta fórmula un significado geométrico.

Problemas de práctica

• CODECHEF: Roads in Stars 
• SPOJ: Maze 
• CODECHEF: Complement Spanning Trees