Вектор Фідлера

Алгебри́чна зв'я́зність графа ${\displaystyle G}$ — це друге з найменших власних значень матриці Кірхгофа графа ${\displaystyle G}$. Це значення більше від нуля тоді й лише тоді, коли G є зв'язним. Це наслідок того, що скільки разів значення 0 з'являється як власне значення матриці Кірхгофа, зі стількох компонент зв'язності й складається граф. Величина цього значення показує наскільки добре зв'язаний весь граф і використовується для аналізу стійкості та синхронізації мереж.

Приклад графа з 6 вершинами, що має діаметр 3, зв'язність 1 і алгебричну зв'язність 0,722

Властивості

Зрізаний ікосаедр або граф фулериту має звичайну зв'язність 3 і алгебричну зв'язність 0,243

Алгебрична зв'язність графа ${\displaystyle G}$ більша від 0 тоді й лише тоді, коли ${\displaystyle G}$ є зв'язним. Більш того, значення алгебричної зв'язності обмежене зверху звичайною (вершинною) зв'язністю графа. Якщо число вершин зв'язного графа дорівнює ${\displaystyle n}$, а діаметр дорівнює ${\displaystyle D}$, алгебрична зв'язність, як відомо, обмежена знизу числом ${\displaystyle {\frac {1}{nD}}}$, і фактично, як показав ^[en], значенням ${\displaystyle {\frac {4}{nD}}}$. Для прикладу, наведеного вище, 4/18 = 0,222 ≤ 0,722 ≤ 1, але для багатьох великих графів алгебрична зв'язність значно ближча до нижньої межі, ніж до верхньої^[].

На відміну від звичайної зв'язності, алгебрична зв'язність залежить як від числа вершин, так і від способу їх з'єднання. У випадкових графах алгебрична зв'язність зменшується зі зростанням числа вершин і збільшується зі зростанням середнього степеня.

Точне визначення алгебричної зв'язності залежить від типу використовуваної матриці Кірхгофа. ^[en] розробила велику теорію, в якій використано нормовані матриці Кірхгофа, що позбавляє значення від числа вершин, так що межі стають дещо іншими.

У моделях синхронізації в мережах, таких як ^[en], матриця Кірхгофа виникає природно, так що алгебрична зв'язність показує, наскільки просто мережа буде синхронізуватися. Однак можна використати й інші показники, такі як середня відстань (характеристика довжини шляху), і фактично алгебрична відстань тісно пов'язана з середньою відстанню (точніше, оберненою до неї величиною).

Алгебрична зв'язність також пов'язана з іншими характеристиками зв'язності, такими як ізопериметричне число, яке обмежене знизу половиною алгебричної зв'язності.

Вектор Фідлера

Спочатку теорію, пов'язану з алгебричною зв'язністю, розробив чеський математик ^[en]. На його честь власний вектор, що відповідає алгебричній зв'язності, названо вектором Фідлера. Вектор Фідлера можна використати для розбиття графа.

Для графа зі вступного розділу вектором Фідлера буде <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}.

Див. також

• Зв'язний граф
• Інваріант графа

Примітки

1. Gross, Yellen, 2004, стр. 314.
2. Gross, Yellen, 2004, стр. 571.
3. Mohar, 1991 стр. 871—898.
4. Synchronization and Connectivity of Discrete Complex Systems [Архівовано 2015-09-23 у Wayback Machine.], Michael Holroyd, International Conference on Complex Systems, 2006.
5. Chung, 1997.
6. Tiago Pereira, Stability of Synchronized Motion in Complex Networks Архівна копія на сайті Wayback Machine.,arXiv:1112.2297v1, 2011.
7. Watts, 2003.
8. Biggs, 1993, стр. 28, 58.
9. Fiedler, 1973.
10. 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) — .
• 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.