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> 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>, так как второе {{---}} безопасное ребро.
→Критерий Тарьяна: Орфография
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
|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>
}}
