394
правки
Изменения
→Доказательство корректности
|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. Тогда существует ребро <tex>x</tex> из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST, получаем цикл в котором <tex>x</tex> не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
}}
