Teorema de Kirchhoff - Encontrando o número de Árvores Geradoras

Problema: Você recebe um grafo não direcionado e conexo (com possíveis várias arestas) representado usando uma matriz de adjacência. Encontre o número de diferentes árvores geradoras deste grafo.

A seguinte fórmula foi comprovada por Kirchhoff em 1847.

Teorema da árvore matricial de Kirchhoff

Seja $A$ a matriz de adjacência do grafo: $A_{u,v}$ é o número de arestas entre $u$ e $v$. Seja $D$ o grau da matriz do grafo: uma matriz diagonal com $D_{u,u}$ sendo o grau do vértice $u$ (incluindo arestas múltiplas e "loops" - arestas que conectam o vértice $u$ com ele mesmo).

A matriz laplaciana(laplacian matrix) do grafo é definida como $L = D - A$. De acordo com o teorema de Kirchhoff, todos os cofatores dessa matriz são iguais entre si e são iguais ao número de árvores geradoras do grafo. O cofator $(i,j)$ de uma matriz é o produto de $(-1)^{i + j}$ com o determinante da matriz que você obtém após remover a $i$-ésima linha e a $j$-ésima coluna. Assim, você pode, por exemplo, excluir a última linha e a última coluna da matriz $L$, e o valor absoluto do determinante da matriz resultante fornecerá o número de árvores geradoras.

O determinante da matriz pode ser encontrado em $O(N^3)$ usando o método de Gauss.

A prova desse teorema é bastante difícil e não é apresentada aqui; para obter um resumo da prova e variações do teorema para grafos sem arestas múltiplas e para grafos direcionados, consulte a Wikipedia para referências.

Relação com as leis de circuito de Kirchhoff

O teorema da árvore matricial de Kirchhoff e as leis de Kirchhoff para circuitos elétricos estão relacionadas. É possível mostrar (usando a lei de Ohm e a primeira lei de Kirchhoff) que a resistência $R_{ij}$ entre dois pontos $i$ e $j$ do circuito será

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

Aqui a matriz matriz $L$ é obtida a partir da matriz de resistências inversas $A$ ($A_{i,j}$ é a inversa da resistência do condutor entre os pontos $i$ e $j$) usando o procedimento descrito no teorema da árvore matricial de Kirchhoff. $T^j$ é a matriz com linha e coluna $j$ removida, $T^{(i,j)}$ é a matriz com duas linhas e duas colunas $i$ e $j$ removidas.

O teorema de Kirchhoff atribui a esta fórmula um significado geométrico.

Problemas