Teorema de Kirchhoff

En matemàtiques, i més concretament en teoria de grafs, el teorema de Kirchhoff, anomenat en referència a Gustav Kirchhoff, és un teorema sobre el nombre d'arbres d'expansió en un gràf, i mostra que aquest nombre es pot calcular en temps polinòmic com el determinant d'una matriu derivada del graf. És una generalització de la fórmula de Cayley que proporciona el nombre d'arbres d'expansió en un graf complet.

El teorema de Kirchhoff es basa en la noció de la matriu laplaciana d'un graf, igual a la diferència entre la matriu de grau del graf (una matriu diagonal amb el grau dels vèrtexs a la diagonal) i la seva matriu d'adjacència (una matriu-(0,1) amb 1 en els llocs corresponents a les entrades on els vèrtexs són adjacents i 0 en cas contrari).

Per a un graf connex G amb n vèrtexs etiquetats, siguin λ₁, λ₂, ..., λ_n-1 els valors propis diferents de zero de la seva matriu laplaciana. Llavors el nombre d'arbres d'expansió de G és

$t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.$

Equivalentment, el nombre d'arbres d'expansió és igual a qualsevol cofactor de la matriu laplaciana de G.