322
правки
Изменения
→Лемма о безопасном ребре
{{Теорема
|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>
