Ru.Wikipedia.Org - Матричная теорема о деревьях

Меню
Главная
Случайная статья
Настройки

Матричная теорема о деревьях
Материал из https://ru.wikipedia.org

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

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

Содержание

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

Пусть

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

Примечания

Kirchhoff, Gustav. Ueber die Auflsung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Strme gefhrt wird (нем.) // Annalen der Physik. — 1847. — Bd. 148, Nr. 12. — S. 497—508. Архивировано 17 мая 2017 года.

Ссылки

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

Литература