Алгебраическая связность (также известный как значение Fiedler или Фидлер собственному значению ) от графа G является вторым наименьшим собственным значением ( с учетом кратных собственных значений отдельно) от лапласиана матрицы из G . [1] Это собственное значение больше 0 тогда и только тогда, когда G - связный граф . Это следствие того факта, что количество раз, когда 0 появляется как собственное значение в лапласиане, равно количеству компонент связности в графе. Величина этого значения отражает, насколько хорошо связан общий график. Он использовался при анализе устойчивости исинхронизируемость сетей.
Характеристики
Алгебраическая связность графа G может быть положительной или отрицательной, даже если G - связный граф . [2] Кроме того, значение алгебраической связности ограничено сверху традиционной (вершинной) связностью графа,. [3] Если количество вершин неориентированного связного графа с неотрицательными весами ребер равно n, а диаметр равен D , алгебраическая связность также известна как ограниченная снизу величиной, [4] и фактически (в результате Брендана Маккея ). [5] Для графа с 6 узлами, показанного выше (n = 6, D = 3), эти границы означают, что 4/18 = 0,222 ≤ алгебраическая связность 0,722 ≤ связность 1.
В отличие от традиционной связности, алгебраическая связность зависит от количества вершин, а также от способа соединения вершин. В случайных графах алгебраическая связность уменьшается с количеством вершин и увеличивается со средней степенью . [6]
Точное определение алгебраической связности зависит от типа используемого лапласиана. Фан Чанг разработал обширную теорию, используя масштабированную версию лапласиана, устранив зависимость от числа вершин, так что оценки несколько отличаются. [7]
В моделях синхронизации в сетях, таких как модель Курамото , матрица Лапласа возникает естественным образом, поэтому алгебраическая связность показывает, насколько легко сеть будет синхронизироваться. [8] Также можно использовать другие меры, такие как среднее расстояние (характерная длина пути) [9], и фактически алгебраическая связность тесно связана со (обратным) средним расстоянием. [5]
Алгебраическая связность также относится к другим атрибутам связности, таким как изопериметрическое число , которое ограничено снизу половиной алгебраической связности. [10]
Вектор Фидлера
Первоначальная теория алгебраической связности была создана Мирославом Фидлером . [11] [12] В его честь собственный вектор, связанный с алгебраической связностью, был назван вектором Фидлера . Вектор Фидлера можно использовать для разбиения графа.
Разбиение графа с помощью вектора Фидлера
Для примера графа во вводном разделе вектор Фидлера равен . Отрицательные значения связаны с плохо связанной вершиной 6 и соседней точкой сочленения , вершиной 4; в то время как положительные значения связаны с другими вершинами. Следовательно, знаки значений в векторе Фидлера можно использовать для разделения этого графа на две составляющие:. В качестве альтернативы значение 0,069 (которое близко к нулю) можно поместить в отдельный класс, разделив график на три компонента:.
Смотрите также
Рекомендации
- ^ Вайсштейн, Эрик В. " Алгебраическая связность ". Материал из MathWorld - веб-ресурса Wolfram.
- Перейти ↑ Wu, Chai Wai (2005). «Алгебраическая связность ориентированных графов». Линейная и полилинейная алгебра . Тейлор и Фрэнсис . 53 (3): 203–223. DOI : 10.1080 / 03081080500054810 .
Даже если G квазисильно связна, что эквивалентно G, содержащему ориентированное остовное дерево, a (G) все еще может быть неположительным, как указывают взрывающаяся звезда и теорема 1.
- ^ JL Гросс и Дж. Йеллен. Справочник по теории графов , CRC Press, 2004, стр. 314.
- ^ JL Гросс и Дж. Йеллен. Справочник по теории графов , CRC Press, 2004, стр. 571.
- ^ a b Боян Мохар , Лапласовский спектр графов , в теории графов, комбинаторике и приложениях , т. 2, Ред. Y. Alavi, G. Chartrand, OR Oellermann , AJ Schwenk, Wiley, 1991, стр. 871–898.
- ^ Синхронизация и связь дискретных сложных систем , Майкл Холройд, Международная конференция по сложным системам, 2006.
- ↑ F. Chung. Теория спектральных графов , Providence, RI: Amer. Математика. Soc., 1997. [1]
- ^ Тьяго Перейра, Устойчивость синхронизированного движения в сложных сетях , arXiv: 1112.2297v1, 2011.
- Перейти ↑ D. Watts, Six Degrees: The Science of a Connected Age , Vintage, 2003.
- ^ Норман Биггс. Алгебраическая теория графов , 2-е изд., Cambridge University Press, 1993, стр. 28 и 58.
- ^ М. Фидлер. «Алгебраическая связность графов», Чехословацкий математический журнал 23 (98) (1973), 298–305.
- ^ М. Фидлер. «Лапласиан графов и алгебраическая связность», Комбинаторика и теория графов (Варшава, 1987), Публикации Банахского центра 25 (1) (1989), 57–70.