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

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

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

Властивості

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

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

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

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

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

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

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

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

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

Див. також

Примітки

Шаблон:Reflist

Література

  1. ↑ Шаблон:Harvnb, стр. 314.
  2. ↑ Шаблон:Harvnb, стр. 571.
  3. ↑ 3,0 3,1 Шаблон:Harvnb стр. 871—898.
  4. ↑ Synchronization and Connectivity of Discrete Complex Systems Шаблон:Webarchive, Michael Holroyd, International Conference on Complex Systems, 2006.
  5. ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Шаблон:Wayback,arXiv:1112.2297v1, 2011.
  6. ↑ Шаблон:Harvnb, стр. 28, 58.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Алгебрична_зв%27язність&oldid=9719