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

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

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

Формулировка

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

Пример

граф	3 его остовных дерева
${\displaystyle {\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&-&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\\mid &&\mid \\2&-&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\&\smallsetminus &\mid \\2&-&3\end{matrix}}}$

Для графа G с матрицей смежности ${\displaystyle A={\begin{bmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{bmatrix}}}$  получаем: ${\displaystyle M={\begin{bmatrix}2&-1&-1&0\\-1&2&-1&0\\-1&-1&3&-1\\0&0&-1&1\end{bmatrix}}}$.

Алгебраическое дополнение, например, элемента M_{1, 2} есть ${\displaystyle (-1)^{(1+2)}{\begin{vmatrix}-1&-1&0\\-1&3&-1\\0&-1&1\end{vmatrix}}=3}$, что совпадает с количеством остовых деревьев.

Следствия

Из матричной теоремы выводится

• Формула Кэли — число остовных деревьев полного графа ${\displaystyle K_{n}}$ равно ${\displaystyle n^{n-2}}$.
• Число остовных деревьев полного двудольнoгo графа ${\displaystyle K_{m,n}}$ равно ${\displaystyle m^{n-1}\cdot n^{m-1}}$.

Обобщения

Теорема обобщается на случай мультиграфов и взвешенных графов. Для взвешенного графа алгебраические дополнения элементов матрицы Кирхгофа равны сумме по всем остовным деревьям произведений весов всех их рёбер. Частный случай получается, если взять веса равными 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. Архивировано 17 мая 2017 года.

Ссылки

• Теорема Кирхгофа

Литература