Conexión algebraica

La conectividad algebraica del grafo G es el segundo de los valores propios  mínimos de la matriz de Kirchhoff del grafo G [1] . Este valor es mayor que cero si y solo si el grafo G es conexo . Esto es consecuencia del hecho de que el número de veces que el valor 0 aparece como un valor propio de la matriz de Kirchhoff, el gráfico consta de tantas componentes conectadas. El valor de este valor refleja qué tan bien está conectado todo el gráfico y se utiliza para analizar la estabilidad y la sincronización de las redes.

Propiedades

La conectividad algebraica de un grafo G es mayor que 0 si y solo si G es conexo . Además, el valor de la conectividad algebraica está acotado desde arriba por la conectividad habitual (vértice) de un gráfico [2] . Si el número de vértices de un gráfico conexo es n y el diámetro es D , se sabe que la conexión algebraica está limitada por debajo por el número [3] y, de hecho, como muestra Brendan McKay , por el valor [4] . Para el ejemplo anterior, 4/18 = 0.222 ≤ 0.722 ≤ 1, pero para muchas gráficas grandes la conectividad algebraica está mucho más cerca del límite inferior que del superior. .

A diferencia de la conectividad ordinaria, la conectividad algebraica depende tanto del número de vértices como de la forma en que están conectados. En grafos aleatorios , la conectividad algebraica disminuye con el aumento del número de vértices y aumenta con el aumento del grado medio [5] .

La definición exacta de una conexión algebraica depende del tipo de matriz de Kirchhoff utilizada. Feng Chang desarrolló una extensa teoría que utiliza matrices de Kirchhoff normalizadas, que eliminan el número de vértices, de modo que los límites se vuelven algo diferentes [6] .

En los modelos de sincronización en redes, como el modelo de Kuramoto , la matriz de Kirchhoff ocurre de forma natural, de modo que la conectividad algebraica indica qué tan fácil se sincronizará la red [7] . Sin embargo, se pueden utilizar otros indicadores, como la distancia media (característica de la longitud del camino) [8] , y de hecho la distancia algebraica está estrechamente relacionada con la distancia media (más precisamente, su valor recíproco) [4] .

La conexión algebraica también está relacionada con otras características de la conexión, como el número isoperimétrico , que está acotado por debajo de la mitad del valor de la conexión algebraica [9] .

Vector de Fiedler

Inicialmente, la teoría relacionada con la conexión algebraica fue desarrollada por el matemático checo Miroslav Fidler [10] [11] . En su honor , el vector propio correspondiente a la conexión algebraica se denomina vector de Fiedler . El vector de Fiedler se puede utilizar para dividir un gráfico.

Para el gráfico de la sección introductoria, el vector de Fiedler será <0.415; 0,309; 0,069; −0,221; 0,221; −0,794>. Los valores negativos corresponden al vértice 6 mal conectado y el punto de articulación adyacente , el vértice 4, mientras que los valores positivos corresponden al resto de vértices. El signo de los elementos del vector de Fiedler se puede utilizar para dividir el gráfico en dos componentes: {1, 2, 3, 5} y {4, 6}. O puede poner el valor 0,069 (que es el más cercano a cero) en su propia clase, dividiendo el gráfico en tres componentes: {1, 2, 5}, {3} y {4, 6}.

Véase también

Notas

  1. ↑ Weisstein, Eric W. " Conectividad algebraica Archivado el 18 de enero de 2015 en Wayback Machine ". En el sitio web de MathWorld.
  2. ↑ Gross, Yellen, 2004 , página 314.
  3. ↑ Gross, Yellen, 2004 , página 571.
  4. ↑ 1 2 Mohar, 1991 págs. 871-898.
  5. ↑ Sincronización y conectividad de sistemas complejos discretos Archivado el 23 de septiembre de 2015 en Wayback Machine , Michael Holroyd, Conferencia internacional sobre sistemas complejos, 2006.
  6. ↑ Chung, 1997 .
  7. ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Archivado el 18 de enero de 2016 en Wayback Machine , arXiv: 1112.2297v1 , 2011.
  8. ↑ Vatios, 2003 .
  9. ↑ Biggs, 1993 , págs. 28, 58.
  10. ↑ Fiedler, 1973 .
  11. ↑ Fiedler, 1989 .

Literatura