title: Teorema di Kirchhoff
text: # 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 |
  | - | - |
  | | ${\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 |
  | - | - |
  | | ${\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.
  
  