Алгебри чна зв я зність графа G displaystyle G це друге з найменших власних значень матриці Кірхгофа графа G displaystyl

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

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

Властивості

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

Алгебрична зв'язність графа $G$ більша від 0 тоді й лише тоді, коли $G$ є зв'язним. Більш того, значення алгебричної зв'язності обмежене зверху звичайною (вершинною) зв'язністю графа. Якщо число вершин зв'язного графа дорівнює $n$ , а діаметр дорівнює $D$ , алгебрична зв'язність, як відомо, обмежена знизу числом ${\frac {1}{nD}}$ , і фактично, як показав ^[en], значенням ${\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}.

Див. також

Примітки

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) — .
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.

[1] Gross, Yellen, 2004, стр. 314.

[2] Gross, Yellen, 2004, стр. 571.

[Mohar-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.

[FOOTNOTEChung1997-5] Chung, 1997.

[6] Tiago Pereira, Stability of Synchronized Motion in Complex Networks Архівна копія на сайті Wayback Machine.,arXiv:1112.2297v1, 2011.

[FOOTNOTEWatts2003-7] Watts, 2003.

[8] Biggs, 1993, стр. 28, 58.

[FOOTNOTEFiedler1973-9] Fiedler, 1973.

[FOOTNOTEFiedler1989-10] Fiedler, 1989.