Опишите алгоритм, который определяет, существуют ли 2 разных MST

Question

Пусть G = (V, E) - взвешенный, связанный и неориентированный граф. Опишите эффективный алгоритм, который решает, есть ли ровно два различных MSTS в G.

предыдущий вопрос, который я уже решил было намного проще: Опишите эффективный алгоритм, который решает, есть ли в точности один MST в G.

Вот как я решил последний вопрос:

Мы запускаем алгоритм Kruskal, а затем окрашиваем края нового MST в синий цвет, а остальные края - красным.

Затем я использовал еще один простой алгоритм, который мы видели (который использует Kruskal), который находит MST в графе, который содержит максимальное количество красных краев, что означает, что это MST в графе G независимо от ребер 'color, и каждый другой MST не может содержать больше красных краев, а MST алгоритм находит.

Теперь существует только один MST, если алгоритм нашел тот же MST (содержащий все синие края).

Другой вопрос здесь кажется намного более сложным. Я попытался использовать алгоритм, описанный выше, а также попытался использовать различные другие трюки, но ни один из них не сработал.

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

Я был бы признателен за любую помощь, Спасибо

Answer 1

я мог бы быть underthinking это, но ваш подход кажется излишне сложным. Чтобы определить, были ли 2 разных MST, я бы начал с запуска Kruskal, чтобы получить первый MST. Затем вы просто запускаете его снова и видите, можете ли вы избежать перехвата с первого MST.

На каждом шаге Kruskal вы добавляете самый дешевый край, который соединяет 2 ранее несвязанных компонента. Поэтому вам нужно сортировать ребра по массе и проходить через них, добавляя их в MST, если они соединяют 2 несвязанных компонента. Когда есть несколько MST, вы достигнете точки, где вы можете выбрать между двумя ребрами того же веса, которые соединяют одни и те же компоненты.

Когда вы запустили Kruskal один раз, вы знаете, какие края находятся в вашем MST. Если вы запустите его во второй раз, вы снова отсортируете края по весу и добавьте к вашему графику самые дешевые края (которые соединяют 2 несвязанных компонента). Однако, если у вас есть выбор, чтобы добавить 2 ребра, которые соединяют одни и те же компоненты, вы можете взять край, который вы не сделали в первый раз. Конечным результатом будет другой MST (не содержащий одного края), а действительный MST, поскольку вы полностью управляете правилами Крускала.

Вы в основном просто делаете Kruskal, но меняете свой брелок для кромок с одинаковым весом. Итерируйте процедуру, чтобы найти еще более разные MST. Если вы хотите узнать, есть ли всего 2 MST, вы должны попробовать найти третий MST.