1632
правки
Изменения
м
Легко заметить<tex> \Rightarrow </tex> Докажем, что остовное дерево, не удовлетворяющее условиюсостоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребер на циклах, тогда оно не минимально. Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла<tex> A </tex> не минимально, то его можно получить остов с меньшим весомулучшить, добавив это значит есть ребро в остов, которое имеет наименьший вес на цикле и удалив самое тяжелое ребро из циклане принадлежит дереву. Если же это условие Следовательно, дерево построено не выполнилось ни для одного на минимальных ребрах в циклах {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра, то вес остова при добавлении не изменитсяна каждом цикле.
Теперь докажемЗаметим, что дерево <tex>KA </tex>состоит полностью из безопасных ребер, удовлетворяющее условию, минимально:так как на каждом шаге добавлялось безопасное ребро.
{{Утверждение|statement=Для любого разреза Теперь, рассмотрим какой-нибудь разрез <tex>\langle (S, T ) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, причем <tex> u \ranglein S </tex>, а <tex> v \in T </tex>. Найдем путь в котором ребро изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex>uvv </tex> {{. Так как они находятся в разных компонентах связности, то какое---}} единственноенибудь ребро <tex> (a, пересекающее его в b) \notin A</tex> тоже будет пересекать разрез <tex>K(S, T) </tex>. Очевидно, вес этого ребра минимален среди всех ребер что <tex>Gw(u, v) \leqslant w(a, b) </tex>, пересекающих этот разрезтак как первое {{---}} безопасное ребро.
|proof=Рассмотрим Следовательно, любое ребро не принадлежащее <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.По условию теоремы, вес <tex>abA</tex> не меньше веса любого ребра на этом пути.При этом легче ребер принадлежащих <tex>abA </tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез.Но единственное такое ребро в остовном дереве {{---}} это <tex>uv</tex>.Следовательно, <tex>w(uv) \le w(ab)</tex>цикле.}}
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
rollbackEdits.php mass rollback
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
|proof=
'''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>
}}
== См.также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Минимально узкое остовное дерево]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Алгоритм Прима]]
==ЛитератураИсточники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
