Algebraisk koppling

Den algebraiska anslutningen för grafen G  är den andra av de minimala egenvärdena för Kirchhoff-matrisen för grafen G [1] . Detta värde är större än noll om och endast om grafen G är ansluten . Detta är en konsekvens av det faktum att antalet gånger värdet 0 visas som ett egenvärde för Kirchhoff-matrisen, grafen består av så många sammankopplade komponenter. Värdet på detta värde återspeglar hur väl hela grafen är ansluten och används för att analysera stabilitet och synkronisering av nätverk.

Egenskaper

Den algebraiska kopplingen för en graf G är större än 0 om och endast om G är ansluten . Dessutom begränsas värdet av algebraisk anslutning ovanifrån av den vanliga (vertex) anslutningen för en graf [2] . Om antalet hörn av en sammankopplad graf är n och diametern är D , är den algebraiska kopplingen känd för att vara begränsad underifrån av talet [3] , och faktiskt, som visas av Brendan McKay , av värdet [4] . För exemplet ovan är 4/18 = 0,222 ≤ 0,722 ≤ 1, men för många stora grafer är den algebraiska anslutningen mycket närmare den nedre gränsen än den övre .

Till skillnad från vanlig anslutning beror algebraisk anslutning både på antalet hörn och på hur de är anslutna. I slumpmässiga grafer minskar den algebraiska kopplingen med en ökning av antalet hörn och ökar med en ökning av medelgraden [5] .

Den exakta definitionen av en algebraisk koppling beror på vilken typ av Kirchhoff-matris som används. Feng Chang utvecklade en omfattande teori som använder normaliserade Kirchhoff-matriser, som gör sig av med antalet hörn, så att gränserna blir något annorlunda [6] .

I synkroniseringsmodeller i nätverk, som Kuramoto-modellen , förekommer Kirchhoff-matrisen naturligt, så att den algebraiska anslutningen indikerar hur lätt nätverket kommer att synkroniseras [ 7] . Däremot kan andra indikatorer användas, såsom medelavståndet (karakteristiskt för banans längd) [8] , och i själva verket är det algebraiska avståndet nära relaterat till medelavståndet (mer exakt, dess ömsesidiga värde) [4] .

Den algebraiska kopplingen är också relaterad till andra egenskaper hos kopplingen, såsom det isoperimetriska talet , som begränsas under av halva värdet av den algebraiska kopplingen [9] .

Fiedler vektor

Till en början utvecklades teorin om algebraisk koppling av den tjeckiske matematikern Miroslav Fidler [10] [11] . Till hans ära benämns egenvektorn som motsvarar den algebraiska kopplingen Fiedlervektorn . Fiedler-vektorn kan användas för att partitionera en graf.

För grafen från det inledande avsnittet kommer Fiedler-vektorn att vara <0,415; 0,309; 0,069; -0,221; 0,221; -0,794>. Negativa värden motsvarar dåligt anslutna vertex 6 och den intilliggande artikulationspunkten , vertex 4, medan positiva värden motsvarar resten av hörnen. Tecknet för elementen i Fiedler-vektorn kan alltså användas för att dela upp grafen i två komponenter - {1, 2, 3, 5} och {4, 6}. Eller så kan du sätta värdet 0,069 (som är närmast noll) i sin egen klass och dela upp grafen i tre komponenter - {1, 2, 5}, {3} och {4, 6}.

Se även

Anteckningar

  1. ↑ Weisstein, Eric W. " Algebraisk anslutning arkiverad 18 januari 2015 på Wayback Machine ." På MathWorlds hemsida.
  2. ↑ Gross, Yellen, 2004 , s. 314.
  3. ↑ Gross, Yellen, 2004 , s. 571.
  4. ↑ 1 2 Mohar, 1991 s. 871-898.
  5. ↑ Synkronisering och anslutning av diskreta komplexa system Arkiverad 23 september 2015 på Wayback Machine , Michael Holroyd, International Conference on Complex Systems, 2006.
  6. ↑ Chung, 1997 .
  7. ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Arkiverad 18 januari 2016 på Wayback Machine , arXiv: 1112.2297v1 , 2011.
  8. ↑ Watts, 2003 .
  9. ↑ Biggs, 1993 , s. 28, 58.
  10. ↑ Fiedler, 1973 .
  11. ↑ Fiedler, 1989 .

Litteratur