- Матричная теорема о деревьях
-
Матричная теорема о деревьях (Matrix tree theorem), также известная как Теорема Кирхгофа — теорема теории конечных графов.
Содержание
Теорема Кирхгофа-Трента
Пусть
— связный помеченный граф с матрицей Кирхгофа
. Все алгебраические дополнения матрицы Кирхгофа
равны между собой и их общее значение есть число остовных деревьев графа
.
Можно расширить теорему на случай мультиграфов и взвешенных графов. Тогда алгебраические дополнения элементов матрицы Кирхгофа для взвешенного графа будут равны сумме произведений проводимости всех остовов. Частный случай получается, если взять проводимости равными 1: сумма произведений проводимостей остовов будет равна числу остовов.Доказательство
Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.Пример
граф G каркасы (3 шт) Для графа G с матрицей смежности
получаем:
.
Алгебраическое дополнение, например, элемента M1, 2 есть
, что совпадает с количеством каркасов.
Ссылки
Категория:- Теория графов
Wikimedia Foundation. 2010.