Изменения
→Доказательство корректности
|statement=Алгоритм Борувки строит MST.
|proof=Очевидно, что агоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки мы можем текущий подграф <tex>T</tex> до MST.
Докажем это по индукции.
База: <tex>n <\tex> = 1(Лемма 1).Переход: Пусть лес <tex>T <\tex> получившийся после <tex>n <\tex> итераций алгоритма можно достроить до MST. Докажем что после <tex>n<\tex>+1-й итерации получившийся лес <tex>T' <\tex> можно достроить до MST.Предположим обратное: <tex>T' <\tex> нельзя достроить до MST. Тогда существует <tex>F <\tex> = MST графа <tex>G<\tex>, содержащее <tex>T <\tex> и не содержащее <tex>T'<\tex>. Тогда рассмотрим цикл получающийся добавлением в <tex>F <\tex> какого-нибудь ребра <tex>x <\tex> из <tex>T' <\tex> - <tex>T<\tex>. На этом цикле имеется ребро большее по весу чем ребро <tex>x<\tex>, иначе компонента для которой <tex>x <\tex> было минимальным ни с кем больше ни связана.Следовательно исходя из критерия тарьяна мы получили противоречие.
}}
