Teorema de Kirchhoff

En el campo matemático de la teoría de grafos, el teorema de Kirchhoff, nombrado por Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo, mostrando que ese número puede ser computado en tiempo polinomial como el determinante de una matriz derivada del grafo. Es una generalización de la fórmula de Cayley que provee el número total de árboles de expansión en un grafo completo.

Teorema de Kirchhoff

El número de árboles abarcadores de un grafo ${G}$ coincide con un cofactor cualquiera de la matriz ${A}_{G}-{D}_{G}$, donde ${A}_{G}$ es la matriz de adyacencia y ${D}_{G}$ es la matriz diagonal cuyas entradas son los grados de los vértices del grafo ${G}$.

Referencias

• Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J. (2008), Combinatorics and Graph Theory, Undergraduate Texts in Mathematics (2nd edición), Springer ..
• Maurer, Stephen B. (1976), «Matrix generalizations of some theorems on trees, cycles and cocycles in graphs», SIAM Journal on Applied Mathematics 30 (1): 143-148, MR 0392635 ..
• Tutte, W. T. (2001), Graph Theory, Cambridge University Press, p. 138, ISBN 978-0-521-79489-3 ..

Enlaces externos

• A proof of Kirchhoff's theorem
• A discussion on the theorem and similar results

• Datos: Q2226691