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

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

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

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

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

Пример

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

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

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

Следствия

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

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

Обобщения

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

Ссылки

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