Teorema de Kirchhoff

En el campo matemático de la teoría de grafos , el teorema de Kirchhoff o teorema del árbol matricial de Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo . Afirma que este número se puede calcular como cualquier cofactor de la matriz laplaciana del grafo . Esto demuestra, en particular, que el número de árboles de expansión se puede calcular a partir de los datos del grafo en tiempo polinomial . El teorema de Kirchhoff es una generalización de la fórmula de Cayley , que proporciona el número de árboles de expansión en un grafo completo . El teorema recibe su nombre del matemático alemán Gustav Kirchhoff , quien lo publicó en 1847. Una traducción al inglés del artículo de Kirchhoff se publicó en 1958. ^{[ 1 ]}

Definiciones y declaración

Sea G un grafo simple no dirigido . Un árbol generador de G es un subgrafo de G que es un árbol con el mismo conjunto de vértices que G. La matriz laplaciana L de G es la diferencia entre la matriz de grados del grafo (la matriz diagonal de grados de los vértices ) y su matriz de adyacencia (una matriz (0,1) con 1 en los lugares que corresponden a entradas donde los vértices son adyacentes y 0 en los demás). Un cofactor de L se obtiene eliminando una fila (digamos la fila i ) y una columna (digamos la columna j ) de L , tomando el determinante de esa matriz más pequeña y multiplicándolo por (-1) ^i+j .

El teorema de Kirchhoff establece que el número de árboles generadores de un grafo es igual a cualquier cofactor de la matriz laplaciana del grafo. (En particular, todos estos cofactores son iguales).

Ejemplo

Primero, construya la matriz laplaciana L para el grafo de diamante de ejemplo G (vea la imagen de la derecha):

L=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right].

A continuación, construya una matriz Q ^* eliminando cualquier fila y cualquier columna de Q . Por ejemplo, al eliminar la fila 1 y la columna 1 se obtiene:

L^{\ast }=\left[{\begin{array}{rrr}3&-1&-1\\-1&3&-1\\-1&-1&2\end{array}}\right].

Finalmente, tomamos el determinante de L ^* , que resulta en 8. El número de árboles de expansión de G , que se muestra a la derecha, también es 8.

Esquema de demostración

(La demostración que sigue se basa en la fórmula de Cauchy-Binet . Un argumento de inducción elemental para el teorema de Kirchhoff se puede encontrar en la página 654 de Moore (2011). ^{[ 2 ]} )

En primer lugar, observemos que la matriz laplaciana tiene la propiedad de que la suma de sus elementos en cualquier fila y cualquier columna es 0. Por lo tanto, podemos transformar cualquier menor en cualquier otro menor sumando filas y columnas, intercambiándolas y multiplicando una fila o una columna por −1. Así, los cofactores son iguales salvo por el signo, y se puede verificar que, de hecho, tienen el mismo signo.

Procedemos a demostrar que el determinante del menor M ₁₁ es el número de árboles de expansión. Sea n el número de vértices del grafo y m el número de sus aristas. La matriz de incidencia E es una matriz de n × m , que se puede definir de la siguiente manera: supongamos que ( i , j ) es la k -ésima arista del grafo y que i < j . Entonces E _ik = 1, E _jk = −1 y todas las demás entradas en la columna k son 0 (véase la matriz de incidencia orientada para comprender esta matriz de incidencia E modificada ). Para el ejemplo anterior (con n = 4 y m = 5):

E=\left[{\begin{array}{rrrrr}1&1&0&0&0\\-1&0&1&1&0\\0&-1&-1&0&1\\0&0&0&-1&-1\end{array}}\right].

Recordemos que el laplaciano L se puede factorizar en el producto de la matriz de incidencia y su transpuesta , es decir, L = EE ^T. Además, sea F la matriz E con su primera fila eliminada, de modo que FF ^T = M ₁₁ .

Ahora la fórmula de Cauchy-Binet nos permite escribir

\det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{\mathrm {T} }\right)=\sum _{S}\det \left(F_{S}\right)^{2}

donde S abarca subconjuntos de [ m ] de tamaño n − 1, y F _S denota la matriz ( n − 1) × ( n − 1) cuyas columnas son las de F con índice en S. Entonces, cada S especifica n − 1 aristas del grafo original, y se puede demostrar que si esas aristas inducen un árbol de expansión, entonces el determinante de F _S es +1 o −1, y si no inducen un árbol de expansión, entonces el determinante es 0. Esto completa la demostración.

Casos particulares y generalizaciones

La fórmula de Cayley

La fórmula de Cayley se deduce del teorema de Kirchhoff como un caso especial, ya que todo vector con 1 en una posición, -1 en otra y 0 en las demás es un vector propio de la matriz laplaciana del grafo completo, cuyo valor propio correspondiente es n . Estos vectores juntos abarcan un espacio de dimensión n - 1, por lo que no existen otros valores propios distintos de cero.

Alternativamente, tenga en cuenta que, dado que la fórmula de Cayley proporciona el número de árboles etiquetados distintos de un grafo completo K _n, necesitamos calcular cualquier cofactor de la matriz laplaciana de K _n . La matriz laplaciana en este caso es

{\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.

Cualquier cofactor de la matriz anterior es n ⁿ⁻² , que es la fórmula de Cayley.

Formulación utilizando los valores propios de la matriz laplaciana.

El teorema se puede formular en términos de los autovalores del laplaciano. Estos autovalores son siempre no negativos y uno de ellos es cero. Para un grafo G dado con n vértices, sea 0 = λ ₀≤λ ₁≤ λ ₂≤ ... ≤ λ _n₋₁ los autovalores de su matriz laplaciana. Entonces, el número t ( G ) de árboles de expansión de G es

t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.

Teorema de Kirchhoff para multigrafos

El teorema de Kirchhoff también se aplica a los multigrafos ; la matriz L se modifica de la siguiente manera:

La entrada q _i,j es igual a − m , donde m es el número de aristas entre i y j ;
Al calcular el grado de un vértice, se excluyen todos los bucles .

La fórmula de Cayley para un multigrafo completo es m ^{n −1} ( n ^{n −1} −( n −1) n ^{n −2} ) por los mismos métodos producidos anteriormente, ya que un grafo simple es un multigrafo con m = 1.

Enumeración explícita de árboles de expansión

El teorema de Kirchhoff se puede reforzar modificando la definición de la matriz laplaciana. En lugar de simplemente contar las aristas que emanan de cada vértice o que conectan un par de vértices, se etiqueta cada arista con una indeterminada y se hace que la entrada ( i , j ) de la matriz laplaciana modificada sea la suma de las indeterminadas correspondientes a las aristas entre los vértices i y j cuando i no es igual a j , y la suma negativa de todas las indeterminadas correspondientes a las aristas que emanan del vértice i cuando i es igual a j .

El determinante de la matriz laplaciana modificada, obtenido al eliminar filas y columnas (de forma similar a como se calcula el número de árboles generadores a partir de la matriz laplaciana original), es un polinomio homogéneo (el polinomio de Kirchhoff) en las indeterminadas correspondientes a las aristas del grafo. Tras agrupar los términos y realizar todas las cancelaciones posibles, cada monomio de la expresión resultante representa un árbol generador formado por las aristas correspondientes a las indeterminadas presentes en dicho monomio. De esta forma, se puede obtener una enumeración explícita de todos los árboles generadores del grafo simplemente calculando el determinante.

Para una demostración de esta versión del teorema, véase Bollobás (1998). ^{[ 3 ]}

Matroides

Los árboles de expansión de un grafo forman las bases de un matroide gráfico , por lo que el teorema de Kirchhoff proporciona una fórmula para el número de bases en un matroide gráfico. El mismo método también puede utilizarse para determinar el número de bases en matroides regulares , una generalización de los matroides gráficos ( Maurer 1976 ) .

Teorema de Kirchhoff para multigrafos dirigidos

El teorema de Kirchhoff se puede modificar para obtener el número de árboles de expansión orientados en multigrafos dirigidos. La matriz Q se construye de la siguiente manera:

La entrada q _i,j para i y j distintos es igual a − m , donde m es el número de aristas de i a j ;
La entrada q _i,i es igual al grado de entrada de i menos el número de bucles en i .

El número de árboles de expansión orientados con raíz en un vértice i es el determinante de la matriz obtenida al eliminar la i -ésima fila y columna de Q.

Conteo que abarca bosques de k componentes

El teorema de Kirchhoff se puede generalizar para contar bosques generadores $de k$ componentes en un grafo no ponderado. ^[⁴^] Un bosque generador de $k componentes es un subgrafo con$ $k$ componentes conexas que contiene todos los vértices y no tiene ciclos, es decir, hay como máximo un camino entre cada par de vértices. Dado un bosque F con componentes conexas de este tipo ${\textstyle F_{1},\dots ,F_{k}}$ , definir su peso ${\textstyle w(F)=|V(F_{1})|\cdot \dots \cdot |V(F_{k})|}$ ser el producto del número de vértices en cada componente. Entonces

\sum _{F}w(F)=q_{k},

donde la suma se realiza sobre todos los bosques que abarcan $k$ componentes y ${\textstyle q_{k}}$ es el coeficiente de ${\textstyle x^{k}}$ del polinomio

(x+\lambda _{1})\dots (x+\lambda _{n-1})x.

El último factor del polinomio se debe al valor propio cero. ${\textstyle \lambda _{n}=0}$ . Más explícitamente, el número ${\textstyle q_{k}}$ se puede calcular como

q_{k}=\sum _{\{i_{1},\dots ,i_{n-k}\}\subset \{1\dots n-1\}}\lambda _{i_{1}}\dots \lambda _{i_{n-k}}.

donde la suma se realiza sobre todos los subconjuntos de ( n − k ) elementos de ${\textstyle \{1,\dots ,n\}}$ . Por ejemplo

{\begin{aligned}q_{n-1}&=\lambda _{1}+\dots +\lambda _{n-1}=\operatorname {tr} Q=2|E|\\q_{n-2}&=\lambda _{1}\lambda _{2}+\lambda _{1}\lambda _{3}+\dots +\lambda _{n-2}\lambda _{n-1}\\q_{2}&=\lambda _{1}\dots \lambda _{n-2}+\lambda _{1}\dots \lambda _{n-3}\lambda _{n-1}+\dots +\lambda _{2}\dots \lambda _{n-1}\\q_{1}&=\lambda _{1}\dots \lambda _{n-1}\end{aligned}}

Dado que un bosque de expansión con n −1 componentes corresponde a una sola arista, el caso k = n − 1 establece que la suma de los autovalores de Q es el doble del número de aristas. El caso k = 1 corresponde al teorema original de Kirchhoff ya que el peso de cada árbol de expansión es n .

La demostración se puede realizar de forma análoga a la demostración del teorema de Kirchhoff. Una invertible $(n-k)\times (n-k)$ La submatriz de la matriz de incidencia corresponde biyectivamente a un bosque generador de k componentes con una elección de vértice para cada componente.

Los coeficientes ${\textstyle q_{k}}$ están hasta el signo de los coeficientes del polinomio característico de Q.

Véase también

Referencias

↑ O'Toole, JB (1958). "Sobre la solución de las ecuaciones obtenidas a partir de la investigación de la distribución lineal de corrientes galvánicas". IRE Transactions on Circuit Theory . 5 (1): 4– 7. doi : 10.1109/TCT.1958.1086426 .
↑ Moore, Cristopher (2011). La naturaleza de la computación . Oxford, Inglaterra. Nueva York: Oxford University Press. ISBN 978-0-19-923321-2OCLC 180753706
↑ Bollobás, Béla (1998). Teoría moderna de grafos . Textos de posgrado en matemáticas. Vol. 184. Nueva York: Springer. doi : 10.1007/978-1-4612-0619-4 . ISBN 978-0-387-98488-9.
↑ Biggs, N. (1993). Teoría algebraica de grafos . Cambridge University Press.

Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J. (2008), Combinatoria y teoría de grafos , Textos de pregrado en matemáticas (2.ª ed.), Springer.
Maurer, Stephen B. (1976), "Generalizaciones matriciales de algunos teoremas sobre árboles, ciclos y cociclos en grafos", SIAM Journal on Applied Mathematics , 30 (1): 143–148 , doi : 10.1137/0130017 , MR 0392635 .
Tutte, WT (2001), Teoría de grafos , Cambridge University Press, pág. 138, ISBN 978-0-521-79489-3.
Chaiken, S.; Kleitman, D. (1978), "Teoremas de árboles matriciales", Journal of Combinatorial Theory, Serie A , 24 (3): 377– 381, doi : 10.1016/0097-3165(78)90067-5 , ISSN 0097-3165