Teorema del árbol matriz

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de junio de 2020; la verificación requiere 1 edición .

Teorema del árbol de matrices o teorema de Kirchhoff : da una expresión para el número de árboles de expansión de un gráfico a través del determinante de una determinada matriz.

Demostrado por Gustav Kirchhoff en 1847; la motivación de este teorema fueron los cálculos de circuitos eléctricos . [una]

Redacción

Sea un gráfico etiquetado conexo con matriz de Kirchhoff . Todos los complementos algebraicos de la matriz de Kirchhoff son iguales entre sí y su valor total es igual al número de árboles generadores del gráfico . $GRAMO$ $METRO$ $METRO$ $GRAMO$

Ejemplo

grafico	3 de sus árboles de expansión
${\begin{matriz}1&&4\\\mid &\smallsetminus &\mid \\2&-&3\end{matriz))$	${\begin{matriz}1&&4\\\mid &&\mid \\2&-&3\end{matriz}}$	${\begin{matriz}1&&4\\\mid &\smallsetminus &\mid \\2&&3\end{matriz))$	${\begin{matriz}1&&4\\&\smallsetminus &\mid \\2&-&3\end{matriz))$

Para un grafo G con matriz de adyacencia , obtenemos: . $A={\begin{bmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{bmatrix}}$ $M={\begin{bmatriz}2&-1&-1&0\\-1&2&-1&0\\-1&-1&3&-1\\0&0&-1&1\end{bmatriz))$

El complemento algebraico, por ejemplo, del elemento M 1, 2 es , que coincide con el número de árboles generadores. $(-1)^{(1+2)}{\begin{vmatriz}-1&-1&0\\-1&3&-1\\0&-1&1\end{vmatriz}}=3$

Consecuencias

Del teorema de la matriz se sigue

Fórmula de Cayley : el número de árboles de expansión de un gráfico completo es . $K_n$ $n^{{n-2}}$
El número de árboles de expansión de un gráfico bipartito completo es . $K_{{m, n}}$ $m^{{n-1}}\cdot n^{{m-1}}$

Generalizaciones

El teorema se generaliza al caso de multigrafos y grafos ponderados. Para un gráfico ponderado, los complementos algebraicos de los elementos de la matriz de Kirchhoff son iguales a la suma de todos los árboles generadores de los productos de los pesos de todas sus aristas. Se obtiene un caso especial si tomamos los pesos iguales a 1: la suma de los productos de los pesos de los esqueletos será igual al número de esqueletos.

Notas

↑ Kirchhof, Gustav. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird (alemán) // Annalen der Physik. - 1847. - Bd. 148 , núm. 12 _ - S. 497-508 .

Enlaces

teorema de Kirchhoff