Матричная теорема о деревьях
Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.
Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.[1][нет в источнике]
Формулировка
[править | править код]Пусть — связный помеченный граф с матрицей Кирхгофа . Все алгебраические дополнения матрицы Кирхгофа равны между собой и их общее значение равно количеству остовных деревьев графа .
Пример
[править | править код]граф | 3 его остовных дерева | ||
---|---|---|---|
|
|
|
|
Для графа G с матрицей смежности получаем: .
Алгебраическое дополнение, например, элемента M1, 2 есть , что совпадает с количеством остовых деревьев.
Следствия
[править | править код]Из матричной теоремы выводится
- Формула Кэли — число остовных деревьев полного графа равно .
- Число остовных деревьев полного двудольнoгo графа равно .
Обобщения
[править | править код]Теорема обобщается на случай мультиграфов и взвешенных графов. Для взвешенного графа алгебраические дополнения элементов матрицы Кирхгофа равны сумме по всем остовным деревьям произведений весов всех их рёбер. Частный случай получается, если взять веса равными 1: сумма произведений весов остовов будет равна количеству остовов.
Примечания
[править | править код]- ↑ Kirchhoff, Gustav. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird (нем.) // Annalen der Physik. — 1847. — Bd. 148, Nr. 12. — S. 497—508. Архивировано 17 мая 2017 года.
Ссылки
[править | править код]Литература
[править | править код]Это заготовка статьи по математике. Помогите Википедии, дополнив её. |