Матрица Кирхгофа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Матрица Кирхгофа (англ. Laplacian matrix) — одно из представлений графа с помощью матрицы. Матрица Кирхгофа используется для подсчета остовных деревьев данного графа (матричная теорема о деревьях), а также в спектральной теории графов.

Определение[править | править вики-текст]

Дан простой граф с вершинами. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:

Также матрицу Кирхгофа можно определить как разность матриц

где — это матрица смежности данного графа, а — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:

Если граф является взвешенным, то определение матрицы Кирхгофа обобщается. В этом случае элементами главной диагонали матрицы Кирхгофа будут суммы весов рёбер, инцидентных соответствующей вершине. Для смежных (связанных) вершин , где — это вес (проводимость) ребра. Для различных не смежных (не связанных) вершин полагается .

Для взвешенного графа матрица смежности записывается с учетом проводимостей ребер, а на главной диагонали матрицы будут суммы проводимостей ребер инцидентных соответствующим вершинам.

Пример[править | править вики-текст]

Пример матрицы Кирхгофа простого графа.

Помеченный граф Матрица Кирхгофа
6n-graf.svg

Свойства[править | править вики-текст]

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

См. также[править | править вики-текст]