Матричная теорема о деревьях

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

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

Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.[1]

Формулировка[править | править вики-текст]

Пусть — связный помеченный граф с матрицей Кирхгофа . Все алгебраические дополнения матрицы Кирхгофа равны между собой и их общее значение равно количеству остовных деревьев графа .

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

граф G остовые деревья (3 шт)

Для графа G с матрицей смежности   получаем: .

Алгебраическое дополнение, например, элемента M1, 2 есть , что совпадает с количеством остовых деревьев.

Обобщения[править | править вики-текст]

Теорема обобщается на случай мультиграфов и взвешенных графов. Для взвешенного графа алгебраические дополнения элементов матрицы Кирхгофа равны сумме произведений проводимости всех остовов. Частный случай получается, если взять проводимости равными 1: сумма произведений проводимостей остовов будет равна количеству остовов.


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

  1. Kirchhoff, Gustav Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird (нем.) // Annalen der Physik. — 1847. — Bd. 148, Nr. 12. — S. 497—508.

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]