- Матрица Кирхгофа
-
Матрица Кирхгофа (Laplacian matrix) — одно из представлений графа с помощью матрицы. Матрица Кирхгофа используется для подсчета остовных деревьев данного графа (матричная теорема о деревьях), а также используется в спектральной теории графов.
Содержание
Определение
Дан простой граф с вершинами. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:
Также матрицу Кирхгофа можно определить как разность матриц
где — это матрица смежности данного графа, а — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:
Если граф является взвешенным, то определение матрицы Кирхгофа обобщается. В этом случае элементами главной диагонали матрицы Кирхгофа будут суммы проводимостей инцидентных ребер соответствующей вершины. Для смежных (связанных) вершин где — это вес (проводимость) ребра. Для различных несмежных (несвязанных) вершин полагается .
Для взвешенного графа матрица смежности записывается с учетом проводимостей ребер, а на главной диагонали матрицы будут суммы проводимостей ребер инцидентных соответствующим вершинам.
Пример
Пример матрицы Кирхгофа простого графа.
Помеченный граф Матрица Кирхгофа Свойства
- Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
- Определитель матрицы Кирхгофа равен нулю:
- Матрица Кирхгофа простого графа симметрична:
- Все алгебраические дополнения симметричной матрицы Кирхгофа равны между собой — постоянная матрицы Кирхгофа. Для простого графа значение данной постоянной совпадает с числом всех возможных остовов графа (см. Матричная теорема о деревьях).
- Если взвешенный граф представляет собой электрическую сеть, то миноры матрицы Кирхгофа позволяют вычислить резистивное расстояние (resistance distance) между точками и данной сети:
,
здесь — постоянная (алгебраическое дополнение) матрицы Кирхгофа, а — алгебраическое дополнение 2-го порядка, то есть определитель матрицы, получающейся из матрицы Кирхгофа вычеркиванием двух строк и двух столбцов .
Существует алгоритм восстановления матрицы Кирхгофа по матрице сопротивлений .- 0 является собственным значением матрицы (соответствующих собственный вектор — все единицы), кратность его равна числу связных компонент графа.
- Остальные собственные значения положительны. Второе по малости значение Фидлер назвал индексом связности графа, его с. вектор — вектор Фиддлера.
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.См. также
Категории:- Типы матриц
- Теория графов
Wikimedia Foundation. 2010.