1632
правки
Изменения
м
Легко заметить<tex> \Rightarrow </tex> Докажем, что остовное дерево, не удовлетворяющее условиюсостоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребер на циклах, тогда оно не минимально. Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла<tex> A </tex> не минимально, то его можно получить остов с меньшим весомулучшить, добавив это значит есть ребро в остов, которое имеет наименьший вес на цикле и удалив самое тяжелое ребро из циклане принадлежит дереву. Если же это условие Следовательно, дерево построено не выполнилось ни для одного на минимальных ребрах в циклах {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра, то вес остова при добавлении не изменитсяна каждом цикле.
Рассмотрим общий алгоритм построения минимального остовного дерева: '''function''' Gentric MST(G): A = dfs(i, a, b, c, w, Ch) a[x] = max(a[x]Следовательно, b[i] + w[x][i] - с[i]) любое ребро не принадлежащее <font color = darkgreentex>// по формуле выше, но без b[x] (прибавим его один раз в конце) A</font color = darkgreentex> b[x] += с[i] a[x] += b[x] не легче ребер принадлежащих <font color = darkgreentex>// так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину xA </font color = darkgreentex> c[x] = max(a[x], b[x])на этом цикле.
Для доказательства минимальности <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>
Заметим, что дерево <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>, так как первое {{---}} безопасное ребро.
}}
== См.также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Минимально узкое остовное дерево]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Алгоритм Прима]]
==ЛитератураИсточники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
