matriz laplaciana
En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada laplaciana gráfica , matriz de admitancia, matriz de Kirchhoff o laplaciana discreta , es una representación matricial de una gráfica . Nombrada en honor a Pierre-Simon Laplace , la matriz laplaciana gráfica se puede ver como una forma de matriz del operador de Laplace discreto negativo en un gráfico que se aproxima al laplaciano continuo negativo obtenido por el método de diferencias finitas .
La matriz laplaciana se relaciona con muchas propiedades útiles de un gráfico. Junto con el teorema de Kirchhoff , se puede utilizar para calcular el número de árboles de expansión para un gráfico dado. El corte más escaso de un gráfico se puede aproximar a través del segundo valor propio más pequeño de su Laplaciano por la desigualdad de Cheeger . La descomposición espectral de la matriz laplaciana permite construir incrustaciones de baja dimensión que aparecen en muchas aplicaciones de aprendizaje automático y determina un diseño espectral en el dibujo de gráficos .
La matriz laplaciana es la más fácil de definir para un gráfico simple , pero es más común en aplicaciones para un gráfico ponderado en los bordes, es decir, con pesos en sus bordes, las entradas de la matriz de adyacencia del gráfico . La teoría de gráficos espectrales relaciona las propiedades de un gráfico con un espectro, es decir, los valores propios y los vectores propios de las matrices asociadas con el gráfico, como su matriz de adyacencia o la matriz laplaciana. Los pesos desequilibrados pueden afectar indeseablemente el espectro de la matriz, lo que lleva a la necesidad de normalización (una escala de columna/fila de las entradas de la matriz) que da como resultado una adyacencia normalizada y matrices laplacianas.
Dado un grafo simple con vértices , su matriz laplaciana se define por elementos como [1]
donde D es la matriz de grados y A es la matriz de adyacencia del gráfico. Dado que es un gráfico simple, solo contiene 1 o 0 y sus elementos diagonales son todos 0.
Observamos para el gráfico no dirigido que tanto la matriz de adyacencia como la matriz laplaciana son simétricas, y que las sumas de filas y columnas de la matriz laplaciana son todas ceros.
