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.

Dato un grafo connesso G con n vertici, siano ${\displaystyle \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 ${\displaystyle n\times n}$ ${\displaystyle [a_{ij}]}$, dove ${\displaystyle a_{ii}}$ è il grado del vertice i.

grafo	matrice dei gradi
	${\displaystyle {\begin{pmatrix}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{pmatrix}}}$

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

grafo	matrice di adiacenza
	${\displaystyle {\begin{pmatrix}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{pmatrix}}}$

Allora il numero di alberi ricoprenti di G è

${\displaystyle 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.

È 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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica