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

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

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

Властивості

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

Алгебрична зв'язність графа більша від 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}.

Див. також

Примітки

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