Algebraické spojení

Algebraická konektivita grafu G  je druhé z minimálních vlastních čísel Kirchhoffovy matice grafu G [1] . Tato hodnota je větší než nula právě tehdy, když je graf G připojen . Je to důsledek toho, že kolikrát se hodnota 0 objeví jako vlastní hodnota Kirchhoffovy matice, graf se skládá z tolika spojených komponent. Hodnota této hodnoty odráží, jak dobře je celý graf zapojen, a používá se k analýze stability a synchronizace sítí.

Vlastnosti

Algebraická konektivita grafu G je větší než 0 právě tehdy, když je G spojen . Hodnota algebraické konektivity je navíc shora omezena obvyklou (vrcholovou) konektivitou grafu [2] . Pokud je počet vrcholů souvislého grafu n a průměr D , je známo, že algebraické spojení je zespodu ohraničeno číslem [3] , a ve skutečnosti, jak ukazuje Brendan McKay , hodnotou [4] . Ve výše uvedeném příkladu je 4/18 = 0,222 ≤ 0,722 ≤ 1, ale pro mnoho velkých grafů je algebraická konektivita mnohem blíže dolní hranici než horní hranici. .

Na rozdíl od běžné konektivity závisí algebraická konektivita jak na počtu vrcholů, tak na způsobu jejich propojení. V náhodných grafech algebraická konektivita klesá s nárůstem počtu vrcholů a roste s růstem průměrného stupně [5] .

Přesná definice algebraického spojení závisí na typu použité Kirchhoffovy matice. Feng Chang vyvinul rozsáhlou teorii, která používá normalizované Kirchhoffovy matice, které se zbavují počtu vrcholů, takže hranice se poněkud liší [6] .

V modelech synchronizace v sítích, jako je Kuramoto Model , se Kirchhoffova matice vyskytuje přirozeně, takže algebraická konektivita ukazuje, jak snadno se bude síť synchronizovat [7] . Lze však použít i další ukazatele, jako je průměrná vzdálenost (charakteristika délky cesty) [8] , a ve skutečnosti algebraická vzdálenost úzce souvisí s průměrnou vzdáleností (přesněji její převrácenou hodnotou) [4] .

S algebraickým spojením souvisí i další charakteristiky spojení, např. izoperimetrické číslo , které je dole ohraničeno polovinou hodnoty algebraického spojení [9] .

Fiedler vektor

Teorii vztahující se k algebraickému spojení původně rozvinul český matematik Miroslav Fidler [10] [11] . Na jeho počest se vlastní vektor odpovídající algebraickému spojení nazývá Fiedlerův vektor . Fiedlerův vektor lze použít k rozdělení grafu.

Pro graf z úvodní části bude Fiedlerův vektor <0,415; 0,309; 0,069; -0,221; 0,221; -0,794>. Záporné hodnoty odpovídají špatně připojenému vrcholu 6 a sousednímu artikulačnímu bodu , vrcholu 4, zatímco kladné hodnoty odpovídají zbytku vrcholů. Znaménko prvků Fiedlerova vektoru lze tedy použít k rozdělení grafu na dvě složky - {1, 2, 3, 5} a {4, 6}. Nebo můžete vložit hodnotu 0,069 (která je nejblíže nule) do její vlastní třídy a rozdělit graf na tři složky – {1, 2, 5}, {3} a {4, 6}.

Viz také

Poznámky

  1. ↑ Weisstein, Eric W. " Algebraic Connectivity Archived 18 January, 2015 at the Wayback Machine ." Na webu MathWorld.
  2. ↑ Gross, Yellen, 2004 , s. 314.
  3. ↑ Gross, Yellen, 2004 , s. 571.
  4. ↑ 1 2 Mohar, 1991 s. 871-898.
  5. ↑ Synchronizace a konektivita diskrétních komplexních systémů Archivováno 23. září 2015 na Wayback Machine , Michael Holroyd, International Conference on Complex Systems, 2006.
  6. ↑ Chung, 1997 .
  7. ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Archived 18. ledna 2016 na Wayback Machine , arXiv: 1112.2297v1 , 2011.
  8. ↑ Watts, 2003 .
  9. ↑ Biggs, 1993 , s. 28, 58.
  10. ↑ Fiedler, 1973 .
  11. ↑ Fiedler, 1989 .

Literatura