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

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

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

Пусть ${\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: сумма произведений весов остовов будет равна количеству остовов.

Примечания

Ссылки

Литература