Matriz de Kirchhoff

La matriz de Kirchhoff es una de las representaciones de un gráfico finito usando una matriz. La matriz de Kirchhoff representa el operador discreto de Laplace para un gráfico. Se utiliza para contar los árboles de expansión de un gráfico dado ( teorema del árbol matriz ), y también en la teoría de gráficos espectrales .

Definición

Dado un grafo simple con vértices. Entonces, la matriz de Kirchhoff del gráfico dado se definirá de la siguiente manera: $\GRAMO$ ${\ estilo de visualización \ | V (G) | = n}$ ${\displaystyle \ K=(k_{i,j})_{n\veces n))$

\ k_{i,j}:={\begin{casos}\deg(v_{i}),&{\text{if}}\ i=j,\\-1,&{\text{ si}}\ (v_{i},v_{j})\en E(G),\\0,&{\text{de lo contrario}}.\end{casos}}

Además, la matriz de Kirchhoff se puede definir como la diferencia de matrices

{\ estilo de visualización \ K = DA,}

donde es la matriz de adyacencia del gráfico dado, y es la matriz, en cuya diagonal principal están los grados de los vértices del gráfico, y los elementos restantes son ceros: $\A$ ${\ estilo de visualización \ D = (d_{i,j})_{n\veces n))$

\ d_{i,j}:={\begin{casos}\deg(v_{i}),&{\text{si}}\ i=j,\\0,&{\text{de lo contrario }}.\end{casos}}

Si se pondera el gráfico , entonces se generaliza la definición de la matriz de Kirchhoff. En este caso, los elementos de la diagonal principal de la matriz de Kirchhoff serán la suma de los pesos de las aristas incidentes en el vértice correspondiente. Para vértices adyacentes (conectados) , donde es el peso (conductividad) del borde. Para diferentes vértices no adyacentes (no conectados) , . $\k_{i,j}=-c(v_{i},v_{j})$ ${\ estilo de visualización \ c (v_ {i}, v_ {j})}$ ${\ estilo de visualización \ k_ {i, j} = 0}$

\ k_{i,j}:={\begin{cases}\sum \limits _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E( G)\end{matriz pequeña}}\!\!\!\!\!\!c(v_{i},u),&{\text{if}}\ i=j,\\-c(v_{ i},v_{j}),&{\text{if}}\ (v_{i},v_{j})\in E(G),\\0,&{\text{de lo contrario}}.\ fin {casos}}

Para un gráfico ponderado, la matriz de adyacencia se escribe teniendo en cuenta las conductividades de las aristas, y en la diagonal principal de la matriz estarán las sumas de las conductividades de las aristas incidentes en los vértices correspondientes. $\A$ $\D$

\ d_{i,j}:={\begin{cases}\sum \limits _{\begin{smallmatrix}u\in V(G)\\(v_{i},u)\in E( G)\end{matriz pequeña}}\!\!\!\!\!\!c(v_{i},u),&{\text{if}}\ i=j,\\0,&{\ texto{de lo contrario}}.\end{casos}}

Ejemplo

Un ejemplo de una matriz de Kirchhoff para un gráfico simple.

Gráfico etiquetado	matriz de Kirchhoff
	$\left({\begin{matriz}{rrrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0& -1&3&0\\0&0&0&-1&0&1\\\end{matriz}}\right)$

Propiedades

La suma de los elementos de cada fila (columna) de la matriz de Kirchhoff es cero: $\ \sum _{i=1}^{|V(G)|}k_{i,j}=0$ .

El determinante de la matriz de Kirchhoff es cero: ${\ estilo de visualización \ det K = 0}$

La matriz de Kirchhoff de un gráfico simple es simétrica : $\ k_{i,j}=k_{j,i}\quad i,j=1,\ldots,|V(G)|$ .

Todos los complementos algebraicos de la matriz simétrica de Kirchhoff son iguales entre sí: la constante de la matriz de Kirchhoff. Para un gráfico simple, el valor de una constante dada es el mismo que el número de todos los esqueletos posibles del gráfico (consulte el teorema del árbol de matrices ). ${\ estilo de visualización \ K_ {(ij)))$

Si la gráfica ponderada es una red eléctrica, donde el peso de cada arista corresponde a su conductividad , entonces los menores de la matriz de Kirchhoff nos permiten calcular la distancia resistiva entre los puntos y de la red dada: ${\ estilo de visualización \ R_ {ij}}$ $\i$ ${\ estilo de visualización \ j}$ ${\displaystyle \ R_{ij}={\frac {K^{(i,j))){K_{(ij)))))$ , aquí está la constante (complemento algebraico) de la matriz de Kirchhoff, y es el complemento algebraico de segundo orden, es decir, el determinante de la matriz obtenido de la matriz de Kirchhoff al eliminar dos filas y dos columnas . ${\ estilo de visualización \ K_ {(ij)))$ ${\ estilo de visualización \ K ^ {(i, j)))$ ${\ estilo de visualización \ i, j}$

Existe un algoritmo para restaurar la matriz de Kirchhoff a partir de la matriz de resistencia . $R_{ij}$
0 es un valor propio de la matriz (el vector propio correspondiente es todos unos), su multiplicidad es igual al número de componentes conectados del gráfico.
El resto de los valores propios son positivos. Fiedler llamó al segundo valor más pequeño el índice de conectividad del gráfico, el vector propio correspondiente es el vector de Fiedler (que no debe confundirse con el índice de conectividad del gráfico de Randic ).

Matriz de Kirchhoff

Definición

Ejemplo

Propiedades

Véase también