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

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

В алгебраическая связность (также известен как Значение Фидлера или же Собственное значение Фидлера) из график грамм второй по величине собственное значение (подсчитывая несколько собственных значений отдельно) Матрица лапласа из грамм.^[1] Это собственное значение больше 0 тогда и только тогда, когда грамм это связный граф. Это следствие того факта, что количество раз, когда 0 появляется как собственное значение в лапласиане, равно количеству компонент связности в графе. Величина этого значения отражает, насколько хорошо связан общий график. Он использовался при анализе устойчивости и синхронизируемость сетей.

Характеристики

В усеченный икосаэдр или же Бакминстерфуллерен график имеет традиционный возможность подключения из 3, и алгебраическая связность 0,243.

Алгебраическая связность график грамм может быть положительным или отрицательным, даже если грамм это связный граф.^[2] Кроме того, значение алгебраической связности ограничено сверху традиционным (вершинным) возможность подключения графика, ${\displaystyle {\text{algebraic connectivity}}\leq {\text{connectivity}}}$.^[3] Если количество вершин связного неориентированного графа с неотрицательными весами ребер равно п и диаметр является D, алгебраическая связность, как известно, ограничена снизу величиной ${\displaystyle {\text{algebraic connectivity}}\geq {\frac {1}{nD}}}$,^[4] и на самом деле (в результате Брендан МакКей ) к ${\displaystyle {\frac {4}{nD}}}$.^[5] Для графа с 6 узлами, показанного выше (n = 6, D = 3), эти границы означают, что 4/18 = 0,222 ≤ алгебраическая связность 0,722 ≤ связность 1.

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

Точное определение алгебраической связности зависит от типа используемого лапласиана. Фань Чанг разработал обширную теорию, используя масштабированную версию лапласиана, устраняющую зависимость от числа вершин, так что оценки несколько отличаются.^[7]

В моделях синхронизация в сетях, таких как Курамото модель матрица Лапласа возникает естественным образом, поэтому алгебраическая связность показывает, насколько легко сеть будет синхронизироваться.^[8] Другие показатели, например, средний расстояние (характерная длина пути) также может использоваться,^[9] и на самом деле алгебраическая связность тесно связана со (обратным) средним расстоянием.^[5]

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

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

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

Разбиение графа с помощью вектора Фидлера

Для примера графа во вводном разделе вектор Фидлера ${\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}$. Отрицательные значения связаны со слабосвязной вершиной 6, а соседние точка сочленения, вершина 4; а положительные значения связаны с другими вершинами. В приметы значений в векторе Фидлера Таким образом, можно использовать для разделения этого графа на два компонента: ${\textstyle \{1,2,3,5\},\{4,6\}}$. В качестве альтернативы значение 0,069 (которое близко к нулю) можно поместить в отдельный класс, разделив график на три компонента: ${\textstyle \{1,2,5\},\{3\},\{4,6\}}$.

Смотрите также

• Связность (теория графов)
• Свойство графа

Рекомендации

1. Weisstein, Eric W. "Алгебраическая связность. »Из MathWorld - веб-ресурса Wolfram.
2. Ву, Чай Вай (2005). «Алгебраическая связность ориентированных графов». Линейная и полилинейная алгебра. Тейлор и Фрэнсис. 53 (3): 203–223. Дои:10.1080/03081080500054810. Даже если G является квазисильно связным, что эквивалентно G, содержащему ориентированное остовное дерево, a (G) все еще может быть неположительным, как указывают взрывающаяся звезда и теорема 1.
3. Дж. Л. Гросс и Дж. Йеллен. Справочник по теории графов, CRC Press, 2004, стр. 314.
4. Дж. Л. Гросс и Дж. Йеллен. Справочник по теории графов, CRC Press, 2004, стр. 571.
5. Боян Мохар, Лапласовский спектр графов, в Теория графов, комбинаторика и приложения, Vol. 2, Ред. Я. Алави, Г. Шартран, О. Р. Оллерманн, A. J. Schwenk, Wiley, 1991, стр. 871–898.
6. Синхронизация и связность дискретных сложных систем, Майкл Холройд, Международная конференция по сложным системам, 2006 г.
7. F. Chung. Теория спектральных графов, Провиденс, Род-Айленд: амер. Математика. Soc., 1997.[1]
8. Тьяго Перейра, Устойчивость синхронизированного движения в сложных сетях, arXiv: 1112.2297v1, 2011.
9. Д. Уоттс, Шесть степеней: наука соединенного века, Винтаж, 2003.
10. Норман Биггс. Алгебраическая теория графов, 2-е изд., Cambridge University Press, 1993, стр. 28 и 58.
11. М. Фидлер. «Алгебраическая связность графов», Чехословацкий математический журнал 23(98) (1973), 298–305.
12. М. Фидлер. «Лапласиан графов и алгебраическая связность», Комбинаторика и теория графов (Варшава, 1987), Публикации Банахского центра 25(1) (1989), 57–70.