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