Изменения
→Лемма о безопасном ребре
{{Теорема
|statement=
Пусть <tex>\ G = (V, E) </tex> - связный неориентированный граф с действительной весовой функцией <tex> w </tex>, определенной на <tex> E </tex>. Пусть <tex> A </tex> - подмножество <tex> E </tex>, которое входит в некоторое минимальное остовное дерево графа <tex> G </tex>; <tex> (S, V - \setminus S) </tex> - разрез <tex> G </tex>, согласованный с <tex> A </tex> по ребрам, а <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V - \setminus S) </tex>. Тогда ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>.
|proof=
Пусть <tex> T </tex> - минимальное остовное дерево, которое включает в себя <tex> A </tex>. Предположим, что <tex> T </tex> не содержит ребро <tex> (u, v) </tex>, поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево <tex> T^* </tex>, которое включает <tex> A \cup {(u, v)} </tex>, путем использования метода вырезания и вставки, показывая таким образом, что ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>. <br>
При добавлении ребро <tex> (u, v) </tex> образует цикл с ребрами на пути <tex> p </tex> от <tex> u </tex> к <tex> v </tex> в минимальном остовном дереве <tex> T </tex>. Так как вершины <tex> u </tex> и <tex> v </tex> находятся на разных сторонах разреза <tex> (S, V - \setminus S) </tex>, то на пути <tex> p </tex> имеется как минимум одно ребро из <tex> T </tex>, которое пересекает разрез. Пусть таким ребром является ребро <tex> (x, y) </tex>. Ребро <tex> (x, y) </tex> не входит в <tex> A </tex>, поскольку разрез согласован с <tex> A </tex> по ребрам. Так как <tex> (x, y) </tex> является единственным путем от <tex> u </tex> к <tex> v </tex> в <tex> T </tex>, то его удаление разбивает <tex> T </tex> на две компоненты. Добавление ребра <tex> (u, v) </tex> восстанавливает разбиение, образуя новое остовное дерево <tex> T^* </tex>. Покажем, что <tex> T^* </tex> - минимальное остовное дерево. Поскольку <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V - \setminus S) </tex>, и <tex> (x, y) </tex> тоже пересекает этот разрез, то <tex> w(u, v) \le w(x, y) </tex>. Следовательно, <tex> w(T^*) = w(T) - w(x, y) + w(u, v) \le w(T) </tex>. Но <tex> T </tex> - минимальное остовное дерево, так что <tex> w(T) \le w(T^*) </tex>. Значит <tex> T^* </tex> также должно быть минимальным остовным деревом. <br>
Покажем, что <tex> (u, v) </tex> действительно безопасное ребро для <tex> A </tex>. Мы имеем <tex> A \subseteq T^* </tex>, поскольку <tex> A \subseteq T </tex> и <tex> (x, y) \notin A </tex>. Таким образом, <tex> A \cup {(u, v)} \subseteq T^* </tex> и, поскольку <tex> T^* </tex> - минимальное остовное дерево, ребро <tex> (u, v) </tex> безопасно для <tex> A </tex>.
}}
