Изменения

Перейти к: навигация, поиск

Алгоритм Борувки

1 байт добавлено, 21:20, 15 декабря 2012
Доказательство корректности
|proof=Предположим обратное: пусть любое MST графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST.Тогда существует ребро x из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST получаем цикл в котором <tex>x</tex> не максимально т.к оно было минимальным. Тогда, исходя из критерия тарьяна, получаем противоречие.
}}
 
{{Теорема
394
правки

Навигация