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

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

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

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

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

Пример

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

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

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

Следствия

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

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

Обобщения

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

Ссылки

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