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

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

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

Свойства

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

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

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

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

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

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

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

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

Для графа из вводного раздела вектором Фидлера будет <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. « от 18 января 2015 на Wayback Machine .» На сайте MathWorld.
  2. , стр. 314.
  3. , стр. 571.
  4. стр. 871—898.
  5. от 23 сентября 2015 на Wayback Machine , Michael Holroyd, International Conference on Complex Systems, 2006.
  6. .
  7. Tiago Pereira, от 18 января 2016 на Wayback Machine ,arXiv:1112.2297v1, 2011.
  8. .
  9. , стр. 28, 58.
  10. .
  11. .

Литература

  • 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. . — 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.
Источник —

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