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:

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

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:

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) , .

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.

Ejemplo

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

Gráfico etiquetado matriz de Kirchhoff

Propiedades

Véase también