Расчет общего количества охваченных деревьев, содержащих определенный набор ребер

Question

Я попробовал следующий подход:

Сначала я делаю краевое сокращение для всех ребер в данном наборе краев, чтобы сформировать модифицированный график.

Затем я рассчитаю общее количество охваченных деревьев, используя теорему дерева матрицы, от модифицированного графика.

Я хочу знать, правильно ли этот метод, и если есть некоторые другие лучшие методы.

Answer 1

Пусть G - график, пусть E - край, и пусть G / E - тот же график с договорным. Потом,

ПРЕДЛОЖЕНИЕ: Между охватными деревьями G / E существует биекция между охватными деревьями G, содержащих е, и охватывающие деревья G / E.

Это предложение не сложно доказать; Вы лучше понимаете доказательство самостоятельно, а не просто спрашивать других людей, правда ли это. Очевидно, что если у вас есть охваченная T дерево G, которое содержит E, то T / E - это охваченное дерево G / E. Что нужно подумать, это то, что вы также можете зайти назад.

И, как указывает Адам, вы должны быть осторожны, чтобы правильно обрабатывать графики с параллельными краями и графиками с краями из вершины для себя.

Answer 2

Я не знаю, правильно ли это правильно или нет, но вам придется осторожнее о том, что сокращение края может привести к параллельным краям. Вам придется убедиться, что деревья, отличающиеся только тем, какими используются параллельный край, считаются различными.