Teorema di Kirchhoff

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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[modifica | modifica sorgente]

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
6n-graph2.svg \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 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
6n-graph2.svg \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 è

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[modifica | modifica sorgente]

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


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