La conectividad algebraica (también conocido como valor Fiedler o Fiedler valor propio ) de un gráfico de G es el segundo más pequeño valor propio (contando múltiples valores propios por separado) de la matriz laplaciana de G . [1] Este valor propio es mayor que 0 si y solo si G es un gráfico conectado . Este es un corolario del hecho de que el número de veces que 0 aparece como un valor propio en el Laplaciano es el número de componentes conectados en el gráfico. La magnitud de este valor refleja qué tan bien conectado está el gráfico general. Se ha utilizado para analizar la robustez ysincronizabilidad de las redes.
Propiedades
La conectividad algebraica de gráficos no dirigidos con pesos no negativos, siendo la desigualdad estricta si y solo si G está conectado. Sin embargo, la conectividad algebraica puede ser negativa para gráficos dirigidos en general, incluso si G es un gráfico conectado . [2] Además, el valor de la conectividad algebraica está delimitado por la conectividad tradicional (vértice) del gráfico,. [3] Si el número de vértices de un gráfico conectado no dirigido con pesos de aristas no negativos es ny el diámetro es D , también se sabe que la conectividad algebraica está limitada por debajo de, [4] y de hecho (en un resultado debido a Brendan McKay ) por. [5] Para el gráfico con 6 nodos que se muestran arriba (n = 6, D = 3), estas medias limitadas, 4/18 = 0,222 ≤ conectividad algebraica 0,722 ≤ conectividad 1.
A diferencia de la conectividad tradicional, la conectividad algebraica depende del número de vértices, así como de la forma en que se conectan los vértices. En gráficos aleatorios , la conectividad algebraica disminuye con el número de vértices y aumenta con el grado promedio . [6]
La definición exacta de la conectividad algebraica depende del tipo de laplaciano utilizado. Fan Chung ha desarrollado una teoría extensa utilizando una versión reescalada del laplaciano, eliminando la dependencia del número de vértices, de modo que los límites son algo diferentes. [7]
En modelos de sincronización en redes, como el modelo de Kuramoto , la matriz laplaciana surge de forma natural, por lo que la conectividad algebraica da una indicación de la facilidad con la que se sincronizará la red. [8] También se pueden utilizar otras medidas, como la distancia media (longitud de trayectoria característica), [9] y, de hecho, la conectividad algebraica está estrechamente relacionada con la distancia media (recíproca de la). [5]
La conectividad algebraica también se relaciona con otros atributos de conectividad, como el número isoperimétrico , que está limitado por debajo de la mitad de la conectividad algebraica. [10]
Vector de Fiedler
La teoría original relacionada con la conectividad algebraica fue elaborada por Miroslav Fiedler . [11] [12] En su honor, el vector propio asociado con la conectividad algebraica se ha denominado vector de Fiedler . El vector Fiedler se puede utilizar para dividir un gráfico.
Particionar un gráfico usando el vector Fiedler
Para el gráfico de ejemplo en la sección introductoria, el vector de Fiedler es . Los valores negativos están asociados con el vértice 6 mal conectado y el punto de articulación vecino , el vértice 4; mientras que los valores positivos están asociados con los otros vértices. Por lo tanto, los signos de los valores en el vector de Fiedler se pueden utilizar para dividir este gráfico en dos componentes:. Alternativamente, el valor de 0.069 (que es cercano a cero) se puede colocar en una clase propia, dividiendo el gráfico en tres componentes:.
Ver también
Referencias
- ^ Weisstein, Eric W. " Conectividad algebraica ". De MathWorld - Un recurso web de Wolfram.
- ^ Wu, Chai Wai (2005). "Conectividad algebraica de gráficos dirigidos". Álgebra lineal y multilineal . Taylor y Francis . 53 (3): 203–223. doi : 10.1080 / 03081080500054810 .
Incluso si G está casi fuertemente conectado, lo que es equivalente a G que contiene un árbol de expansión dirigido, a (G) todavía puede ser no positivo como lo indican la estrella en explosión y el Teorema 1.
- ^ JL Gross y J. Yellen. Manual de teoría de grafos , CRC Press, 2004, página 314.
- ^ JL Gross y J. Yellen. Manual de teoría de grafos , CRC Press, 2004, página 571.
- ^ a b Bojan Mohar , El espectro laplaciano de gráficos , en Teoría de gráficos, combinatoria y aplicaciones , vol. 2, Ed. Y. Alavi, G. Chartrand, OR Oellermann , AJ Schwenk, Wiley, 1991, págs. 871–898.
- ^ Sincronización y conectividad de sistemas complejos discretos , Michael Holroyd, Conferencia internacional sobre sistemas complejos, 2006.
- ^ F. Chung. Teoría del gráfico espectral , Providence, RI: Amer. Matemáticas. Soc., 1997. [1]
- ^ Tiago Pereira, estabilidad del movimiento sincronizado en redes complejas , arXiv: 1112.2297v1, 2011.
- ^ D. Watts, Six Degrees: The Science of a Connected Age , Vintage, 2003.
- ^ Norman Biggs. Teoría de grafos algebraicos , 2a ed., Cambridge University Press, 1993, págs. 28 y 58.
- ^ M. Fiedler. "Conectividad algebraica de gráficos", Checoslovaco Mathematical Journal 23 (98) (1973), 298-305.
- ^ M. Fiedler. "Laplaciano de gráficos y conectividad algebraica", Combinatoria y teoría de gráficos (Varsovia, 1987), Publicaciones del Centro Banach 25 (1) (1989), 57–70.