Изменения

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

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

Теперь докажем, что Предположим противное: пусть остовное дерево <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\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>abA </tex> пересекает <font color = darkgreen>// нужное ребро находится с помощью [[Лемма о безопасном ребре|леммы о безопасном ребре]] </font color = darkgreen> <tex>A = A \cup \langle S{( u, T v )\rangle} </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>uvтоже будет пересекать разрез <tex> (S, T) </tex>. Таким образомОчевидно, что <tex>w(abu, v) \ge leqslant w(uva, b) </tex>, чтак как первое {{---}} безопасное ребро. т. д Следовательно, любое ребро не принадлежащее <tex> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.