Как мне проверить, имеет ли мой график по крайней мере X минимальных связующих деревьев?

Question

Я ищу эффективный алгоритм поиска, если в графе существует хотя бы «Х» число MST. Любые указатели?

Answer 1

Это не исчерпывает полный алгоритм, но принятый ответ An algorithm to see if there are exactly two MSTs in a graph? (by @j_random_hacker) поднимает точку, которая, вероятно, вам поможет. Взятые из его ответа:

Кроме того, каждый MST может быть получен путем выбора какой-то конкретный способ заказать каждый набор равных весовых ребер, а затем запуск алгоритма Крускала .

Возможно, вы можете написать алгоритм, который использует это, чтобы получить количество MST. Ну, просто прямо используя этот факт, и ничто другое, вероятно, не доходит до территории «эффективного алгоритма», хотя я полагаю, что любой эффективный алгоритм будет использовать пару подобных фактов. Я добавлю больше результатов, если найду.