Teorema di Kirchhoff
Da Wikipedia, l'enciclopedia libera.
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.
[modifica] Teorema di Kirchhoff
Dato un grafo connesso G con n vertici, siano λ1,λ2,...,λ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 
[aij], dove aii è il grado del vertice i.
| grafo | matrice dei gradi |
|---|---|
 |
 |
La matrice di adiacenza è una matrice [aij], dove aij è il numero di archi che uniscono il vertice i e il vertice j
| grafo | matrice di adiacenza |
|---|---|
|
 |
Allora il numero di alberi ricoprenti di G è
In altri termini, il numero di alberi ricoprenti è uguale a qualsiasi cofattore della matrice laplaciana di G.
[modifica] 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.
