394
правки
Изменения
→Доказательство корректности
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex> и <tex>w(e1)!= w(e2)</tex> .
Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
|proof=Предположим обратное: пусть любое MST графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST. Тогда существует ребро <tex>x</tex> из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST получаем цикл в котором <tex>x</tex> не максимально т.к оно было минимальным. Тогда, исходя из [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 критерия тарьяна], получаем противоречие.
}}
