Teorema de kirchhoff
En el campo matemático de la teoría de grafos , el teorema de Kirchhoff o el teorema del árbol de la matriz de Kirchhoff que lleva el nombre de Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un gráfico , lo que muestra que este número puede calcularse en tiempo polinomial como el determinante de la matriz laplaciana de la gráfica. Es una generalización de la fórmula de Cayley que proporciona el número de árboles de expansión en un gráfico completo .
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 unos en los lugares correspondientes a las entradas donde los vértices son adyacentes y ceros en caso contrario).
Para un gráfico conectado dado G con n vértices etiquetados , sean λ 1 , λ 2 , ..., λ n −1 los valores propios distintos de cero de su matriz laplaciana. Entonces el número de árboles de expansión de G es
A continuación, construir una matriz de Q * mediante la supresión de cualquier fila y cualquier columna de Q . Por ejemplo, al eliminar la fila 1 y la columna 1 se obtiene
Finalmente, tome el determinante de Q * para obtener t ( G ), que es 8 para el gráfico de diamante. (Observe que t ( G ) es el (1,1) -cofactor de Q en este ejemplo).
(La siguiente demostración se basa en la fórmula de Cauchy-Binet . En la página 654 de Moore (2011) se puede encontrar un argumento de inducción elemental para el teorema de Kirchhoff. [1] )
