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

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

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

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

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

Примечания

Ссылки

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

Литература

Эта страница в последний раз была отредактирована 1 июня 2023 в 04:35.