Число остовных деревьев по теореме Кирхгофа

Посчитать все разные остовные деревья неориентированного графа точным определителем кофактора лапласиана.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Остовных деревьев: 3

  1. Построен лапласиан графа.
  2. Определитель вычислен точно с учётом знаков перестановок строк.

Метод и условия расчёта

Лапласиан L имеет степени на диагонали и −1 вместо рёбер вне диагонали.

Удаляем одну строку и тот же столбец. Определитель кофактора равен числу остовных деревьев.

Теория к методу

Остовное дерево использует все вершины и часть исходных рёбер, соединяя вершины без циклов. Теорема Кирхгофа превращает количество таких наборов в определитель: из лапласиана удаляют одну строку и одноимённый столбец.

Начните с проверки постановки: граф неориентированный, простой, без петель, все вершины входят в остов. Матрица смежности симметрична, её диагональ нулевая. Названия вершин нужны для задания структуры, но не создают дополнительных деревьев: один и тот же набор рёбер не пересчитывается из-за другого порядка обхода.

Пример: У треугольника степени равны двум. После удаления третьей строки и столбца остаётся матрица [[2,−1],[−1,2]]. Её определитель равен 4−1=3.

Независимый перебор подтверждает три дерева: из трёх рёбер нужно убрать ровно одно, и каждый такой выбор сохраняет связность. Для пути на трёх вершинах выбора уже нет: оба ребра обязательны.

Вопросы по теме

Это минимальное по весу дерево?

Нет. Весов во входе нет; считается количество всех остовов, а не стоимость одного.

Что для несвязного графа?

Остова на всех вершинах нет, поэтому число равно нулю. Для одной вершины принято одно пустое дерево.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.