Изменения

Остовное дерево минимально тогда и только тогда, когда любое ребро для любого ребра, не из дерева является максимальным на циклепринадлежащего остову, цикл, который образуется образуемый этим ребром при его добавлении в деревок остову, не содержит рёбер тяжелее этого ребра.

Если существует реброДокажем, не максимальное что остовное дерево, состоящее из ребер наименьшего веса на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальноециклах {{---}} минимально.

Теперь докажем, что Предположим противное: пусть остовное дерево <tex>TA </tex>состоит из всех минимальных ребер на циклах, удовлетворяющее условию, тогда оно не минимально:.

Для этого покажем, что для любого разреза <tex>\langle S, T \rangle</tex> исходного графа <tex>G</tex>, вес ребра Если <tex>uv \in TA </tex>не минимально, пересекающего этот разрезто его можно улучшить, минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим значит есть ребро <tex>ab \notin T</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> которое имеет наименьший вес на цикле и <tex>b</tex> по не принадлежит дереву <tex>T</tex>. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие.

По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) Leftarrow </tex>, ч. т. д.

Найдем теперь Построим минимальное остовное дерево графа используя [[алгоритм Краскала]]<tex> A </tex>, с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра на каждом цикле. '''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>// нужное ребро находится с помощью [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано выше, равен весу ребра <tex/font color = darkgreen>T </tex>A = A \cup \{( u, пересекающего этот разрез. Поэтому вес получившегося минимального остова <tex>Gv )\} </tex> будет равен весу '''return''' <tex>TA </tex>, что и требовалось.

==ЛитератураИсточники информации==