1
правка
Изменения
м
Рассмотрим общий алгоритм построения минимального остовного дерева Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребер на циклах, тогда оно не минимально. Если <tex> A </tex>не минимально, то его можно улучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, но сначаладерево построено не на минимальных ребрах в циклах {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, ознакомившись с определением [[Лемма о безопасном ребре|безопасного помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра]]на каждом цикле.
В результате алгоритма получится минимальное остовное Заметим, что дерево <tex> A </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> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.
Теперь, рассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, причем <tex> u \in S </tex>, а <tex> v \in T </tex>. Найдем путь, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то какое-нибудь ребро <tex> (a, b) </tex> тоже будет пересекать разрез <tex> (S, T) </tex>. Очевидно, что <tex> w(a, b) \le </tex> веса ребра <tex> w(u, v) </tex>, так как второе - безопасное ребро.
→Критерий Тарьяна: Орфография
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
|proof=
<tex> \Rightarrow </tex>
'''function''' Generic MST(<tex> G </tex>):
<tex> A = \{ \} </tex>
'''while''' <tex> A </tex> не является остовом
'''do''' найти безопасное ребро <tex> ( u, v ) \in E </tex> для <tex> A </tex> <font color = darkgreen>// нужное ребро находится с помощью "Леммы [[Лемма о безопасном ребре" |леммы о безопасном ребре]] </font color = darkgreen>
<tex> A = A \cup \{( u, v )\} </tex>
'''return''' <tex> A </tex>
}}
