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