Conectividad algebraica

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 \mathcal{L}(\Gamma)[1] —por ello se le signa como λ2—. También se denomina salto espectral, gap o parámetro de Fiedler.[2]

Este autovalor es mayor que cero si y sólo si Γ es un grafo conexo. La medida de este valor refleja la conectividad del grafo en general, y se ha utilizado para el análisis de la sincronización de nodos en redes. A medida que λ2 se hace más pequeño el grafo adquiere una estructura más modular.

En los modelos para la sincronización de nodos en redes, como el modelo de Kuramoto, la matriz laplaciana surge de manera natural (a través del laplaciano discreto), por lo que la conectividad algebraica da una idea de la facilidad con la que la red se sincronizará. Sin embargo, otras medidas, tales como la media de la distancia también se puede utilizar,[3] y, de hecho, la conectividad algebraica está estrechamente relacionado con el inverso de la distancia media.[4]

Al autovector asociado a λ2 se le denomina \vec u_2 vector de Fiedler , y se usa para la partición de grafos. Por ejemplo, sea:

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)

El vector de Fiedler es

(0.415, 0.309, 0.069, -0.221, 0.221, -0.794).

Los valores negativos se asocian con el nodo 6, y el punto de articulación entre vecinos, el nodo 4, mientras que los valores positivos están asociados con los otros nodos. El signo de los valores en el vector de Fiedler puede ser utilizado para dividir el gráfos en componentes: {1, 2, 3, 5} y {4, 6}. Por otra parte, el valor de 0,069 (que es cercana a cero) se pueden colocar en una clase propia, la partición del grafo en tres componentes: {1, 2, 5}, {3} y {6 4}.

Este autovalor ha sido investigado ampliamente por ser un invariante muy importante. El principio de Courant-Fischer dice que:[5]

\lambda_2^{\Gamma}=\min_{\begin{array}{r} \vec{u} \perp \vec{1} \\ \vec{u}\neq\vec{0}\end{array}}\frac{(\hat{\mathcal{L}}\vec{u},\vec u)}{(\vec u,\vec u)}

Fiedler obtiene otra expresión para grafos con pesos aμν no nulos:

\lambda_2^{\Gamma}=2n\min_{\begin{array}{r} \vec{u} \perp \vec{1} \\ \vec{u}\neq\vec{0} \end{array}}{\frac{\sum_{\mu\nu}{a_{\mu\nu}(u_{\mu}-u_{\nu})^2}}{\sum_{\mu\nu}{(u_{\mu}-u_{\nu})^2}}}
Aplicaciones

La conectividad algebráica da un límite inferior al diámetro de un grafo Γ:

\mathtt{diam}(\Gamma)\geqslant\frac{4}{n\lambda_2^{\Gamma}}
Referencias
  1. ↑ Weisstein, Eric W. "Algebraic Connectivity." De MathWorld--A Wolfram Web Resource.
  2. ↑ M. Fiedler, "Algebraic Connectivity of Graphs", Czech. Math. J. 23:298--305, 1973
  3. ↑ D. Watts,Six Degrees: The Science of aEdad Conectado, Vintage, 2003.
  4. ↑ Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.
  5. ↑ Nota: \vec{1}=\left(\begin{array}{r} 1 \\ 1 \\ \vdots \\ 1 \\ \end{array}\right) \qquad \vec{0}=\left(\begin{array}{r} 0 \\ 0 \\ \vdots \\ 0 \\ \end{array}\right)

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • 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… …   Wikipedia Español

  • Topología — Para otros usos de este término, véase Topología (desambiguación). Ilustración del Teor …   Wikipedia Español

  • Variedad (matemática) — En una esfera, la suma de los ángulos de un triángulo no es igual a 180°, pues una esfera no es un espacio euclídeo. Sin embargo, localmente, las leyes de la geometría euclídea son buenas aproximaciones. Este ejemplo ilustra cómo la esfera puede… …   Wikipedia Español

  • Portal:Matemática — …   Wikipedia Español

  • Morfología matemática — Una forma (en azul) y su dilatación (en verde) y erosión (en amarillo) morfológica por un elemento estructurante con forma de diamante. La Morfología matemática es una teoría y técnica para el análisis y tratamiento de las estructuras geométricas …   Wikipedia Español

Compartir el artículo y extractos

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