Алгебрична зв'язність
Алгебри́чна зв'я́зність графа — це друге з найменших власних значень матриці Кірхгофа графа . Це значення більше від нуля тоді й лише тоді, коли G є зв'язним. Це наслідок того, що скільки разів значення 0 з'являється як власне значення матриці Кірхгофа, зі стількох компонент зв'язності й складається граф. Величина цього значення показує наскільки добре зв'язаний весь граф і використовується для аналізу стійкості та синхронізації мереж.
Властивості
ред.Алгебрична зв'язність графа більша від 0 тоді й лише тоді, коли є зв'язним. Більш того, значення алгебричної зв'язності обмежене зверху звичайною (вершинною) зв'язністю графа[1]. Якщо число вершин зв'язного графа дорівнює , а діаметр дорівнює , алгебрична зв'язність, як відомо, обмежена знизу числом [2], і фактично, як показав Брендан МакКей[en], значенням [3]. Для прикладу, наведеного вище, 4/18 = 0,222 ≤ 0,722 ≤ 1, але для багатьох великих графів алгебрична зв'язність значно ближча до нижньої межі, ніж до верхньої[джерело?].
На відміну від звичайної зв'язності, алгебрична зв'язність залежить як від числа вершин, так і від способу їх з'єднання. У випадкових графах алгебрична зв'язність зменшується зі зростанням числа вершин і збільшується зі зростанням середнього степеня[4].
Точне визначення алгебричної зв'язності залежить від типу використовуваної матриці Кірхгофа. Фен Чанг[en] розробила велику теорію, в якій використано нормовані матриці Кірхгофа, що позбавляє значення від числа вершин, так що межі стають дещо іншими[5].
У моделях синхронізації в мережах, таких як Модель Курамото[en], матриця Кірхгофа виникає природно, так що алгебрична зв'язність показує, наскільки просто мережа буде синхронізуватися[6]. Однак можна використати й інші показники, такі як середня відстань (характеристика довжини шляху)[7], і фактично алгебрична відстань тісно пов'язана з середньою відстанню (точніше, оберненою до неї величиною)[3].
Алгебрична зв'язність також пов'язана з іншими характеристиками зв'язності, такими як ізопериметричне число, яке обмежене знизу половиною алгебричної зв'язності[8].
Вектор Фідлера
ред.Спочатку теорію, пов'язану з алгебричною зв'язністю, розробив чеський математик Мирослав Фідлер[en][9][10]. На його честь власний вектор, що відповідає алгебричній зв'язності, названо вектором Фідлера. Вектор Фідлера можна використати для розбиття графа.
Для графа зі вступного розділу вектором Фідлера буде <0,415; 0,309; 0,069; −0,221; 0,221; −0,794>. Від'ємні значення відповідають погано зв'язаній вершині 6 і сусідній точці зчленування, вершині 4, а додатні значення відповідають решті вершин. Таким чином, знак елементів вектора Фідлера можна використати для розбиття графа на дві компоненти — {1, 2, 3, 5} і {4, 6}. Або можна значення 0,069 (розташоване ближче до нуля) помістити у свій власний клас, розбивши граф на три компоненти — {1, 2, 5}, {3} і {4, 6}.
Див. також
ред.Примітки
ред.- ↑ Gross, Yellen, 2004, стр. 314.
- ↑ Gross, Yellen, 2004, стр. 571.
- ↑ а б Mohar, 1991 стр. 871—898.
- ↑ Synchronization and Connectivity of Discrete Complex Systems [Архівовано 2015-09-23 у Wayback Machine.], Michael Holroyd, International Conference on Complex Systems, 2006.
- ↑ Chung, 1997.
- ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Архівна копія на сайті Wayback Machine.,arXiv:1112.2297v1, 2011.
- ↑ Watts, 2003.
- ↑ Biggs, 1993, стр. 28, 58.
- ↑ Fiedler, 1973.
- ↑ Fiedler, 1989.
Література
ред.- J.L. Gross,. Yellen. Handbook of Graph Theory. — CRC Press, 2004.
- F. Chung. Spectral Graph Theory. — Providence : RI: Amer. Math. Soc, 1997. — Т. 19. — (Math. Surv. & Monogr.)
- D. Watts. Six Degrees: The Science of a Connected Age. — New York, London : W.W. Norton & company, 2003.
- Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — Т. 67. — (Cambridge Tracts in Mathematics) — ISBN 0-521-20335-X.
- M. Fiedler. Algebraic connectivity of Graphs // Czechoslovak Mathematical Journal. — 1973. — Вип. 23 (98).
- M. Fiedler. Laplacian of graphs and algebraic connectivity // Combinatorics and Graph Theory. — 1989. — Вип. 23.
- Bojan Mohar. The Laplacian Spectrum of Graphs. — Graph Theory, Combinatorics, and Applications. — New York : Wiley, 1991. — Т. 2.