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

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

Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G[1]. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.

Свойства

Усечённый икосаэдр или граф фуллерита имеет обычную связность 3 и алгебраическую связность 0,243

Алгебраическая связность графа G больше 0 в том и только в том случае, если G является связным. Более того, значение алгебраической связности ограничено сверху обычной (вершинной) связностью графа[2]. Если число вершин связного графа равно n, а диаметр равен D, алгебраическая связность, как известно, ограничена снизу числом [3], и фактически, как показал Брендан МакКей[англ.], значением [4]. Для примера, приведённого выше, 4/18 = 0,222 ≤ 0,722 ≤ 1, но для многих больших графов алгебраическая связность много ближе к нижней границе, чем к верхней[].

В отличие от обычной связности алгебраическая связность зависит как от числа вершин, так и от способа их соединения. В случайных графах алгебраическая связность уменьшается с ростом числа вершин и растёт с увеличением средней степени[5].

Точное определение алгебраической связности зависит от типа используемой матрицы Кирхгофа. Фэн Чанг[англ.] разработала обширную теорию, в которой используется нормированные матрицы Кирхгофа, что избавляет значения от числа вершин, так что границы становятся несколько другими[6].

В моделях синхронизации в сетях, таких как Модель Курамото[англ.], матрица Кирхгофа возникает естественным образом, так что алгебраическая связность показывает насколько просто сеть будет синхронизироваться[7]. Однако могут быть использованы и другие показатели, такие как среднее расстояние (характеристика длины пути)[8], и фактически алгебраическое расстояние тесно связано со средней дистанцией (точнее обратной ей величиной)[4].

Алгебраическая связность также связана с другими характеристиками связности, такими как изопериметрическое число, которое ограничено снизу половиной значения алгебраической связности[9].

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

Первоначально теория, связанная с алгебраической связностью, разработана чешским математиком Мирославом Фидлером[англ.][10][11]. В его честь собственный вектор, соответствующий алгебраической связности, носит имя вектор Фидлера. Вектор Фидлера можно использовать для разбиения графа.

Для графа из вводного раздела вектором Фидлера будет <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. Weisstein, Eric W. «Algebraic Connectivity Архивная копия от 18 января 2015 на Wayback Machine.» На сайте MathWorld.
  2. Gross, Yellen, 2004, стр. 314.
  3. Gross, Yellen, 2004, стр. 571.
  4. 1 2 Mohar, 1991 стр. 871—898.
  5. Synchronization and Connectivity of Discrete Complex Systems Архивная копия от 23 сентября 2015 на Wayback Machine, Michael Holroyd, International Conference on Complex Systems, 2006.
  6. Chung, 1997.
  7. Tiago Pereira, Stability of Synchronized Motion in Complex Networks Архивная копия от 18 января 2016 на Wayback Machine,arXiv:1112.2297v1, 2011.
  8. Watts, 2003.
  9. Biggs, 1993, стр. 28, 58.
  10. Fiedler, 1973.
  11. 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.