394
правки
Изменения
→Доказательство корректности
{{Лемма
|id=lemma1
|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> не максимально т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
