Matriz laplaciana
En teoría de grafos la matriz laplaciana — también denominada matriz de admitancia o matriz de Kirchhoff — es una representación matricial de un grafo. Otro tipo de representación matricial la proporciona la matriz de adyacencia, pero la matriz laplaciana es ideal para realizar la teoría espectral de grafos.
Definición
Dado un grafo G con n nodos, la matriz laplaciana se define como:[1]
siendo el grado del nodo i-ésimo . La matriz laplaciana normalizada se define como:[1]
Tomando como la matriz diagonal de elementos de entrada , se tiene que:
con la convención para .
Propiedades
- Relación con la matriz de adyacencias
Cuando el grafo es k-regular se puede observar que:
donde es la matriz de adyacencias y es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:
- .
- Ejemplo
Ejemplo de la representación en forma de grafo de una red y su representación matricial laplaciana:
grafo | matriz laplaciana |
---|---|
![]() |
- Espectro de
Para un grafo y matriz laplaciana , con los autovalores ordenados (el espectro de ) :
- La matriz laplaciana es siempre definida positiva.
- El primer autovalor es siempre nulo; existe un autovector que es siempre . La multiplicidad de indica el número de subgrafos inconexos que hay.
- El segundo autovalor no nulo se denomina conectividad algebraica.[2] Es una medida de la conectividad del grafo. A medida que se hace más pequeño el grafo adquiere una estructura más modular. A través de la percolación a través de un grafo, la sincronización máxima se da para el valor más alto posible de . También se denomina salto espectral, gap o parámetro de Fiedler.[3]
Referencias
- Weisstein, Eric W. «Laplacian Matrix». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- Del inglés: Algebraic connectivity, Weisstein, Eric W. "Algebraic Connectivity." De MathWorld--A Wolfram Web Resource.
- M. Fiedler, "Algebraic Connectivity of Graphs", Czech. Math. J. 23:298--305, 1973