Число остовных деревьев по теореме Кирхгофа
Посчитать все разные остовные деревья неориентированного графа точным определителем кофактора лапласиана.
Ваш пример
Разбор примера
Остовных деревьев: 3
- Построен лапласиан графа.
- Определитель вычислен точно с учётом знаков перестановок строк.
Метод и условия расчёта
Лапласиан L имеет степени на диагонали и −1 вместо рёбер вне диагонали.
Удаляем одну строку и тот же столбец. Определитель кофактора равен числу остовных деревьев.
Теория к методу
Остовное дерево использует все вершины и часть исходных рёбер, соединяя вершины без циклов. Теорема Кирхгофа превращает количество таких наборов в определитель: из лапласиана удаляют одну строку и одноимённый столбец.
Начните с проверки постановки: граф неориентированный, простой, без петель, все вершины входят в остов. Матрица смежности симметрична, её диагональ нулевая. Названия вершин нужны для задания структуры, но не создают дополнительных деревьев: один и тот же набор рёбер не пересчитывается из-за другого порядка обхода.
Пример: У треугольника степени равны двум. После удаления третьей строки и столбца остаётся матрица [[2,−1],[−1,2]]. Её определитель равен 4−1=3.
Независимый перебор подтверждает три дерева: из трёх рёбер нужно убрать ровно одно, и каждый такой выбор сохраняет связность. Для пути на трёх вершинах выбора уже нет: оба ребра обязательны.
Вопросы по теме
Это минимальное по весу дерево?
Нет. Весов во входе нет; считается количество всех остовов, а не стоимость одного.
Что для несвязного графа?
Остова на всех вершинах нет, поэтому число равно нулю. Для одной вершины принято одно пустое дерево.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.