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

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

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

ФормулировкаПравить

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

ПримерПравить

граф 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.

СсылкиПравить

ЛитератураПравить