Matriz laplaciana

En el campo matemático de la teoría de grafos , la matriz laplaciana , también llamada grafo laplaciano , matriz de admitancia, matriz de Kirchhoff o laplaciana discreta , es una representación matricial de un grafo . La matriz laplaciana se puede utilizar para encontrar 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 una gráfica se puede aproximar a través del segundo valor propio más pequeño de su laplaciano por la desigualdad de Cheeger. También se puede utilizar para construir incrustaciones de baja dimensión , que pueden ser útiles para una variedad de aplicaciones de aprendizaje automático .

Dado un gráfico simple con vértices, su matriz laplaciana se define como: ^[1]${\ Displaystyle G}$${\ Displaystyle n}$${\ textstyle L_ {n \ times n}}$

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 unos o ceros y sus elementos diagonales son todos ceros.${\ textstyle G}$${\ textstyle A}$

En el caso de gráficos dirigidos , se puede utilizar tanto el grado inferior como el superior , según la aplicación.

donde es el grado del vértice .${\ Displaystyle \ operatorname {grado} (v_ {i})}$${\ Displaystyle i}$

Los elementos de están dados por${\ textstyle L ^ {\ text {sym}}}$

Este GIF muestra la progresión de la difusión, según lo resuelto por la técnica grafica laplaciana. Un gráfico se construye sobre una cuadrícula, donde cada píxel del gráfico está conectado a sus 8 píxeles limítrofes. Los valores en la imagen luego se difunden sin problemas a sus vecinos a lo largo del tiempo a través de estas conexiones. Esta imagen en particular comienza con tres valores de puntos fuertes que se transmiten lentamente a sus vecinos. Todo el sistema finalmente se establece en el mismo valor en equilibrio.