Teorema de Kirchhoff
Ir a la navegación
Ir a la búsqueda
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 coincide con un cofactor cualquiera de la matriz , donde es la matriz de adyacencia y es la matriz diagonal cuyas entradas son los grados de los vértices del grafo .