Teorema di Kirchhoff

In teoria dei grafi, il teorema di Kirchhoff è un teorema sul numero di alberi ricoprenti in un grafo. Esso prende il nome da Gustav Kirchhoff, ed è una generalizzazione della formula di Cayley che fornisce il numero di alberi ricoprenti in un grafo completo.

Teorema di Kirchhoff

Dato un grafo connesso G con n vertici, siano ${\lambda }_1,{\lambda }_2,...,{\lambda }_{n-1}$ gli autovalori non nulli della matrice laplaciana di G. La matrice laplaciana di G è definita come

L: = D − A

con D matrice dei gradi di G e A matrice di adiacenza di G. Il numero di archi incidenti in un vertice n ∈ G prende nome grado di n. La matrice dei gradi è una matrice diagonale $n\times n$ $[a_{ij}]$, dove $a_{ii}$ è il grado del vertice i.

grafo	matrice dei gradi
	$\left(\begin{array}{cccccc}4& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$

La matrice di adiacenza è una matrice $n\times n$ $[a_{ij}]$, dove $a_{ij}$ è il numero di archi che uniscono il vertice $i$ e il vertice $j$

grafo	matrice di adiacenza
	$\left(\begin{array}{cccccc}2& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)$

Allora il numero di alberi ricoprenti di G è

$G=\frac{1}{n}{\lambda }_1{\lambda }_2\cdots {\lambda }_{n-1}.$

In altri termini, il numero di alberi ricoprenti è uguale a qualsiasi cofattore della matrice laplaciana di G.

Note

È facile dimostrare che la formula di Cayley è un caso particolare del teorema di Kirchhoff: ogni vettore con 1 in un posto, -1 in un altro posto, e 0 in ogni altro posto è un autovettore della matrice laplaciana del grafo completo, ed il suo corrispondente autovalore è n. Questi vettori coprono insieme uno spazio di dimensione n-1, pertanto non vi sono altri autovalori non nulli.