MAXimal

добавлено: 5 Nov 2008 20:17
редактировано: 23 Aug 2010 22:24

Матричная теорема Кирхгофа. Нахождение количества остовных деревьев

Задан связный неориентированный граф своей матрицей смежности. Кратные рёбра в графе допускаются. Требуется посчитать количество различных остовных деревьев этого графа.

Приведённая ниже формула принадлежит Кирхгофу (Kirchhoff), который доказал её в 1847 г.

Матричная теорема Кирхгофа

Возьмём матрицу смежности графа G, заменим каждый элемент этой матрицы на противоположный, а на диагонале вместо элемента Ai,i поставим степень вершины i (если имеются кратные рёбра, то в степени вершины они учитываются со своей кратностью). Тогда, согласно матричной теореме Кирхгофа, все алгебраические дополнения этой матрицы равны между собой, и равны количеству остовных деревьев этого графа. Например, можно удалить последнюю строку и последний столбец этой матрицы, и модуль её определителя будет равен искомому количеству.

Определитель матрицы можно найти за O (N3) с помощью метода Гаусса или метода Краута.

Доказательство этой теоремы достаточно сложно и здесь не приводится (см., например, Приезжев В.Б. "Задача о димерах и теорема Кирхгофа").

Связь с законами Кирхгофа в электрической цепи

Между матричной теоремой Кирхгофа и законами Кирхгофа для электрической цепи имеется удивительная связь.

Можно показать (как следствие из закона Ома и первого закона Кирхгофа), что сопротивление Rij между точками i и j электрической цепи равно:

Rij = |T(i,j)| / |Tj|

где матрица T получена из матрицы A обратных сопротивлений проводников (Aij - обратное число к сопротивлению проводника между точками i и j) преобразованием, описанным в матричной теореме Кирхгофа, а обозначение T(i) обозначает вычёркивание строки и столбца с номером i, а T(i,j) - вычёркивание двух строк и столбцов i и j.

Теорема Кирхгофа придаёт этой формуле геометрический смысл.