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

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

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

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

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

Алгебраическая связность график грамм может быть положительным или отрицательным, даже если грамм это связный граф.[2] Кроме того, значение алгебраической связности ограничено сверху традиционным (вершинным) возможность подключения графика, .[3] Если количество вершин связного неориентированного графа с неотрицательными весами ребер равно п и диаметр является 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 (которое близко к нулю) можно поместить в отдельный класс, разделив график на три компонента: .

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

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

  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.