Matriz laplaciana

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 L:=(\ell_{i,j})_{n \times n} se define como:[1]

\ell_{i,j}:=
\begin{cases}
\kappa_i & \mbox{si}\ i = j \\
-1 & \mbox{si}\ i \neq j\ \mbox{y}\ n_i \mbox{ es adyacente a } n_j \\
0 & \mbox{otro caso}.
\end{cases}

siendo \kappa_i el grado del nodo i-ésimo n_i. La matriz laplaciana normalizada \mathcal{L}:=(\hat\ell_{i,j})_{n \times n} se define como:[1]

\hat\ell_{i,j}:=
\begin{cases}
1 & \mbox{si}\ i = j\ \mbox{y}\ \kappa_i \neq 0\\
-\frac{1}{\sqrt{\kappa_i\kappa_j}} & \mbox{si}\ i \neq j\ \mbox{y}\ n_i \mbox{ es adyacente a } n_j \\
0 & \mbox{otro caso}.
\end{cases}

Tomando \hat T como la matriz diagonal de elementos (i,i) de entrada \kappa_i, se tiene que:

\hat\mathcal{L}=\hat T^{-1/2}\hat L\hat T^{-1/2}

con la convención (\hat T^{-1})_{v,v}=0 para \kappa_v=0.

Propiedades[editar]

Relación con la matriz de adyacencias

Cuando el grafo \Gamma es k-regular se puede observar que:

\hat\mathcal{L}=\hat\mathbb{I}-\frac{1}{k}\hat A

donde A es la matriz de adyacencias y \hat\mathbb{I} es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:

\hat\mathcal{L}=\hat T^{-1/2}\hat L\hat T^{-1/2}=\hat\mathbb{I}-\hat T^{-1/2}\hat A\hat T^{-1/2}.
Ejemplo

Ejemplo de la representación en forma de grafo de una red y su representación matricial laplaciana:

grafo matriz laplaciana
6n-graf.svg \left(\begin{array}{rrrrrr}
 2 & -1 &  0 &  0 & -1 &  0\\
-1 &  3 & -1 &  0 & -1 &  0\\
 0 & -1 &  2 & -1 &  0 &  0\\
 0 &  0 & -1 &  3 & -1 & -1\\
-1 & -1 &  0 & -1 &  3 &  0\\
 0 &  0 &  0 & -1 &  0 &  1\\
\end{array}\right)
Espectro de \hat\mathcal{L}

Para un grafo \Gamma y matriz laplaciana L(\Gamma), con los autovalores ordenados (el espectro de L) \lambda_0\leqslant\lambda_1\leqslant\dotsc\leqslant\lambda_{n-1}:

  1. La matriz laplaciana es siempre definida positiva.
  2. El primer autovalor \lambda_0=0 es siempre nulo; existe un autovector que es siempre [1,1,\dots,1]. La multiplicidad de \lambda_0 indica el número de subgrafos inconexos que hay.
  3. El segundo autovalor no nulo \lambda_2 se denomina conectividad algebraica.[2] Es una medida de la conectividad del grafo. A medida que \lambda_2 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 \lambda_2. 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 inglés). MathWorld. 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