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

Question

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

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

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

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

Answer 1

Пусть G - граф, пусть e - ребро, и пусть G / e - тот же граф с сокращенным e. Тогда

Предложение: Существует биекция между связующими деревьями G, содержащими e, и связующими деревьями G / e.

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

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

Answer 2

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