Алгебраическая связность
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G[1]. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
Свойства
Алгебраическая связность графа G больше 0 в том и только в том случае, если G является связным. Более того, значение алгебраической связности ограничено сверху обычной (вершинной) связностью графа[2]. Если число вершин связного графа равно n, а диаметр равен D, алгебраическая связность, как известно, ограничена снизу числом [3], и фактически, как показал Шаблон:Нп5, значением [4]. Для примера, приведённого выше, 4/18 = 0,222 ≤ 0,722 ≤ 1, но для многих больших графов алгебраическая связность много ближе к нижней границе, чем к верхнейШаблон:Нет АИ.
В отличие от обычной связности алгебраическая связность зависит как от числа вершин, так и от способа их соединения. В случайных графах алгебраическая связность уменьшается с ростом числа вершин и растёт с увеличением средней степени[5].
Точное определение алгебраической связности зависит от типа используемой матрицы Кирхгофа. Шаблон:Не переведено 5 разработала обширную теорию, в которой используется нормированные матрицы Кирхгофа, что избавляет значения от числа вершин, так что границы становятся несколько другимиШаблон:Sfn.
В моделях синхронизации в сетях, таких как Шаблон:Не переведено 5, матрица Кирхгофа возникает естественным образом, так что алгебраическая связность показывает насколько просто сеть будет синхронизироваться[6]. Однако могут быть использованы и другие показатели, такие как среднее расстояние (характеристика длины пути)Шаблон:Sfn, и фактически алгебраическое расстояние тесно связано со средней дистанцией (точнее обратной ей величиной)[4].
Алгебраическая связность также связана с другими характеристиками связности, такими как изопериметрическое число, которое ограничено снизу половиной значения алгебраической связности[7].
Вектор Фидлера
Первоначально теория, связанная с алгебраической связностью, разработана чешским математиком Шаблон:Нп5Шаблон:SfnШаблон:Sfn. В его честь собственный вектор, соответствующий алгебраической связности, носит имя вектор Фидлера. Вектор Фидлера можно использовать для разбиения графа.
Для графа из вводного раздела вектором Фидлера будет <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}.
См. также
Примечания
Литература
- ↑ Weisstein, Eric W. «Algebraic Connectivity Шаблон:Wayback.» На сайте MathWorld.
- ↑ Шаблон:Harvnb, стр. 314.
- ↑ Шаблон:Harvnb, стр. 571.
- ↑ 4,0 4,1 Шаблон:Harvnb стр. 871—898.
- ↑ Synchronization and Connectivity of Discrete Complex Systems Шаблон:Wayback, Michael Holroyd, International Conference on Complex Systems, 2006.
- ↑ Tiago Pereira, Stability of Synchronized Motion in Complex Networks Шаблон:Wayback,arXiv:1112.2297v1, 2011.
- ↑ Шаблон:Harvnb, стр. 28, 58.