Matriz laplaciana

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.

Contenido

Definición

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 κi el grado del nodo i-ésimo ni. 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 κi, se tiene que:

No se pudo entender (La conversión a PNG ha sido errónea): \hat\mathcal{L}=\hat T^{-1/2}\hat L\hat T^{-1/2}

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

Propiedades

Relación con la matriz de adyacencias

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

No se pudo entender (La conversión a PNG ha sido errónea): \hat\mathcal{L}=\hat\mathbb{I}-\frac{1}{k}\hat A

donde A es la matriz de adyacencias y No se pudo entender (La conversión a PNG ha sido errónea): \hat\mathbb{I}

es la identidad. Para un grafo sin vértices aislados, tenemos entonces que:
No se pudo entender (La conversión a PNG ha sido errónea): \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 No se pudo entender (La conversión a PNG ha sido errónea): \hat\mathcal{L}

Para un grafo Γ y matriz laplaciana L(Γ), 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 λ0 = 0 es siempre nulo; existe un autovector que es siempre [1,1,\dots,1]. La multiplicidad de λ0 indica el número de subgrafos inconexos que hay.
  3. El segundo autovalor no nulo λ2 se denomina conectividad algebraica.[2] Es una medida de la conectividad del grafo. A medida que λ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 λ2. También se denomina salto espectral, gap o parámetro de Fiedler.[3]

Véase también

Referencias

  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

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Matriz de adyacencia — La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias. Contenido 1 Construcción de la matriz a partir de un grafo 1.1 Ejemplo de grafo no dirigido 1.2 Ejemplo de grafo dir …   Wikipedia Español

  • Conectividad algebraica — Dado un grafo Γ, la conectividad algebraica de un grafo es el segundo autovalor más pequeño no nulo de la matriz laplaciana [1] por ello se le signa como λ2 . También se denomina salto espectral, gap o parámetro de Fiedler.[2] Este autovalor es… …   Wikipedia Español

  • Vector propio y valor propio — Fig. 1. En esta transformación de la Mona Lisa, la imagen se ha deformado de tal forma que su eje vertical no ha cambiado. (nota: se han recortado las esquinas en la imagen de la derecha) …   Wikipedia Español

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde… …   Wikipedia Español

  • Raíz de la unidad — Saltar a navegación, búsqueda En matemática, las raíces n ésimas de la unidad, o números de de Moivre, son todos los números complejos que resultan 1 cuando son elevados a una potencia dada n. Se puede demostrar que están localizados en el… …   Wikipedia Español

  • Ecuaciones de Maxwell — Las cuatro ecuaciones de Maxwell describen todos los fenómenos electromagnéticos, aquí se muestra la inducción magnética por medio de una co …   Wikipedia Español

  • Átomos en moléculas — Ejemplo de cuencas atómicas de un cristal de peruskita KCaF3 En amarillo los átomos de Calcio, en verde los Fluor y en rojo los Potasio. El planteamiento de la teoría de átomos en móleculas es un modelo químico cuántico que caracteriza el enlace… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”