1632
правки
Изменения
м
Пусть нам дано минимальное Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <tex> A </tex>состоит из всех минимальных ребер на циклах, тогда оно не минимально. Если <tex> A </tex> не минимально, то его можно улучшить, значит есть ребро, которое получилось имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в результате циклах {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра минимального веса на каждом цикле.
Пусть у нас есть минимальное остовное дерево <tex> A </tex>, состоящее из минимальных ребер на циклах. Докажем, что такое дерево минимально.
Предположим противное. В дереве <tex> A </tex> не все минимальные ребра на циклах. Тогда найдется цикл, в котором есть ребро <tex> (u, v) \notin A</tex>, которое легче остальных ребер этого цикла, включая ребро <tex> (a, b) \in A</tex>. Следовательно, можно получить остов с меньшим весом, удалив ребро <tex> (a, b) </tex>, и, добавив <tex> (u, v) </tex>. Поэтому, дерево содержащее не минимальные ребра на циклах не минимально {{---}} противоречие.
rollbackEdits.php mass rollback
<tex> \Rightarrow </tex>
'''function''' Generic MST(<tex> G </tex>):
Теперь, рассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, причем <tex> u \in S </tex>, а <tex> v \in T </tex>. Найдем путь в изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то какое-нибудь ребро <tex> (a, b) \notin A</tex> тоже будет пересекать разрез <tex> (S, T) </tex>. Очевидно, что <tex> w(u, v) \leqslant w(a, b) </tex>, так как первое {{---}} безопасное ребро.
Следовательно, любое ребро не принадлежащее <tex> \notin A</tex> не легче ребер принадлежащих <tex> \in A </tex> на этом цикле. <tex> \Leftarrow </tex>
}}
