Teorema de Kirchhoff:
- El teorema de Kirchhoff es un teorema que se utiliza el número de árboles de expansión en un gráfico In-Complete, lo que demuestra que este número se puede calcular en tiempo polinómico como el determinante de una matriz derivada del gráfico.
- El teorema de Kirchhoff se basa en la noción de la matriz laplaciana de un gráfico que es igual a la diferencia entre la matriz de grados del gráfico (una matriz diagonal con grados de vértice en las diagonales) y su matriz de adyacencia (una matriz de (0,1) con 1 en lugares correspondientes a entradas donde los vértices son adyacentes y 0 en caso contrario).
- De manera equivalente, el número de árboles de expansión es igual a cualquier cofactor de la matriz laplaciana de G.
- La matriz laplaciana o matriz de Kirchhoff es una representación matricial de un gráfico, que se puede utilizar para encontrar muchas propiedades útiles de un gráfico.
- Junto con el teorema de Kirchhoff, se puede usar para calcular el número de árboles de expansión para un gráfico dado.
