1632
правки
Изменения
м
Рассмотрим общий алгоритм построения минимального остовного дерева Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <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>, так как первое {{---}} безопасное ребро.
rollbackEdits.php mass rollback
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
|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>
Следовательно, любое ребро не принадлежащее <tex> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.
== См.также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Минимально узкое остовное дерево]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Алгоритм Прима]]
==Источники информации==
