La conectividad algebraica (también conocida como valor de Fiedler o valor propio de Fiedler en honor a Miroslav Fiedler ) de un grafo G es el segundo valor propio más pequeño (contando los valores propios múltiples por separado) de la matriz laplaciana de G. [1] Este valor propio es mayor que 0 si y solo si G es un grafo conexo . Esto es un corolario del hecho de que la cantidad de veces que 0 aparece como valor propio en el laplaciano es la cantidad de componentes conectados en el grafo. La magnitud de este valor refleja qué tan bien conectado está el grafo en general. Se ha utilizado para analizar la robustez y la sincronizabilidad de las redes.
La conectividad algebraica de grafos no dirigidos con pesos no negativos, siendo la desigualdad estricta si y solo si G es conexo. Sin embargo, la conectividad algebraica puede ser negativa para grafos dirigidos generales, incluso si G es un grafo conexo . [2] Además, el valor de la conectividad algebraica está acotado por encima por la conectividad (de vértice) tradicional de un grafo, , a menos que el grafo sea completo (la conectividad algebraica de un grafo completo K n es su orden n ). [3] Si el número de vértices de un grafo conexo no dirigido con pesos de arista no negativos es n y el diámetro es D , también se sabe que la conectividad algebraica está acotada por debajo por , [4] y de hecho (en un resultado debido a Brendan McKay ) por . [5] Para el gráfico con 6 nodos mostrado arriba (n=6,D=3) estos valores límite significan, 4/18 = 0,222 ≤ conectividad algebraica 0,722 ≤ conectividad 1.
A diferencia de la forma tradicional de conectividad de grafos , definida por configuraciones locales cuya eliminación desconectaría el grafo, la conectividad algebraica depende del número global de vértices, así como de la forma en que se conectan los vértices. En grafos 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 los 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 la red se sincronizará. [8] También se pueden utilizar otras medidas, como la distancia media (longitud de la trayectoria característica), [9] y, de hecho, la conectividad algebraica está estrechamente relacionada con la (recíproca de la) distancia media. [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]
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 ha sido denominado vector de Fiedler . El vector de Fiedler se puede utilizar para particionar un grafo.
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 mal conectado 6 y el punto de articulación vecino , 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 usar 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: o se puede mover a la otra partición , como se muestra en la imagen. Los valores al cuadrado de los componentes del vector de Fiedler, que suman uno ya que el vector está normalizado, se pueden interpretar como probabilidades de los puntos de datos correspondientes que se asignarán a la partición basada en signos.
Incluso si G está cuasi-fuertemente conectado, lo que es equivalente a que G contenga 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.
