Будет ли минимальное охваченное дерево не иметь только те края, указанные в недвижимость цикла?[Дубликат]

Question

<в сторону CLASS="S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль= «Статус»>

Этот вопрос уже имеет ответ здесь :

Какие края не в каком-либо MST? (1 ответ)

Закрыто 4 месяца назад .

Answer 1

Давайте скажем, что край $ e $ в $ g $ / strong> Если существует цикл в $ g $ , в котором $ e $ имеет максимальный вес.

Определите $ {\ cal b}={e ~ | ~ e $ bad в $ g \} $ - быть коллекцией всех плохих краев.

Ваш вопрос - это ли график $ (g - {\ cal b}) $ MST $ G $ (при условии, что все тяжелые веса отличаются). Ответ да!

Для того, чтобы доказать, что это достаточно, чтобы показать, что $ (g - {\ cal b}) $ acyclic.

Предположим напротив, что $ (g - {\ cal b}) $ содержит цикл, скажем, $ C $ . Соблюдайте, что $ C $ - это цикл в $ G $ . Пусть $ E ^ * $ Быть край максимального веса в цикле $ C $ . Теперь $ E ^ * $ - это BAD EDGE, так что не должно быть графом $ (G - {\ cal b}) $ на первом месте. Это показывает, что $ (g - {\ cal b}) $ - ациклический.

Answer 2

Извините, если я не понял ваш вопрос, но то, что я думаю, вы имели в виду, это спросить, возможно ли вам не быть в MST, если этот край не в цикле.

Вот мой ответ.

Давайте предположим, что у нас есть край (U, V) в графе G, это не является частью цикла.Это будет означать, что нет пути от U до V, который не является краем (U, V). Если край (u, v) не был в MST, это будет означать, что нет пути от вас V в этом MST, что означает, что MST будет отключен, и, следовательно, не является MST. Следовательно, если край не является частью цикла, он должен быть в MST графика.