Teorema de Kirchhoff

En el camp matemàtic de la teoria de grafos, la teorema de Kirchhoff, nomenat per Gustav Kirchhoff és una teorema sobre el número d'arbres d'expansió en un grafo, mostrant que eixe número pot ser computat en temps polinomial com el determinant d'una matriu derivada del grafo. És una generalisació de la fòrmula de Cayley que proveïx el número total d'arbres d'expansió en un grafo complet.

Teorema de Kirchhoff

El número d'arbres abarcadores d'un grafo $G$ coincidix en un cofactor qualsevol de la matriu $A_G-D_G$, a on $A_G$ és la matriu de adyacencia i $D_G$ és la matriu diagonal les entrades de la qual són els graus dels vèrtiços del grafo $G$.