Алгебрична зв'язність

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

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

Властивості

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• 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.