Dado un grafo , la conectividad algebraica de un grafo es el primer autovalor más pequeño no nulo de la matriz laplaciana Weisstein, Eric W. "Algebraic Connectivity." De MathWorld--A Wolfram Web Resource. —por ello se le signa como —. También se denomina salto espectral, gap o parámetro de Fiedler.M. Fiedler, "Algebraic Connectivity of Graphs", Czech. Math. J. 23:298--305, 1973

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 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, D. Watts,Six Degrees: The Science of aEdad Conectado, Vintage, 2003. y, de hecho, la conectividad algebraica está estrechamente relacionado con el inverso de la distancia media.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.

Al autovector asociado a se le denomina vector de Fiedler , y se usa para la partición de grafos. Por ejemplo, sea: grafomatriz laplaciana175px 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:Nota:

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

Aplicaciones La conectividad algebraica da un límite inferior al diámetro de un grafo :

Referencias

Categoría:Estructura de datos Categoría:Conectividad de grafos Categoría:Invariantes de grafos