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

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

Для графа 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: сумма произведений весов остовов будет равна количеству остовов.

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