MAXimal | |
добавлено: 5 Nov 2008 20:17 Содержание [скрыть] Матричная теорема Кирхгофа. Нахождение количества остовных деревьевЗадан связный неориентированный граф своей матрицей смежности. Кратные рёбра в графе допускаются. Требуется посчитать количество различных остовных деревьев этого графа. Приведённая ниже формула принадлежит Кирхгофу (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. Теорема Кирхгофа придаёт этой формуле геометрический смысл.
|