Matriz laplaciana

Elemento algebraico matricial para representar grafos.

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 editar

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 editar

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  )  :

  1. La matriz laplaciana es siempre definida positiva.
  2. El primer autovalor   es siempre nulo; existe un autovector que es siempre  . La multiplicidad de   indica el número de subgrafos inconexos que hay.
  3. 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]

Véase también editar

Referencias editar

  1. a b Weisstein, Eric W. «Laplacian Matrix». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  2. Del inglés: Algebraic connectivity, Weisstein, Eric W. "Algebraic Connectivity." De MathWorld--A Wolfram Web Resource.
  3. M. Fiedler, "Algebraic Connectivity of Graphs", Czech. Math. J. 23:298--305, 1973