Изменения
→Доказательство корректности
==Доказательство корректности==
{{Лемма1
|id=lemma1
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>.
Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
|proof=Предположим обратное: пусть любое MST графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST.Тогда существует ребро x из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST получаем цикл в котором <tex>x</tex> не максимально т.к оно было минимальным. Тогда, исходя из критерия тарьяна, получаем противоречие.
}}
{{Теорема
|id=th1.
|statement=Алгоритм Борувки строит MST.
|proof=Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки мы можем текущее дерево <tex>T</tex> до MST.Докажем это по индукции.
База: n = 1(Лемма 1).
Переход: Пусть дерево получившееся после n итераций алгоритма можно достроить до MST.
}}
