1
правка
Изменения
м
→Критерий Тарьяна: Орфография
Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально.
Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребрах ребер на циклах, тогда оно не минимально.
Если <tex> A </tex> не минимально, то его можно улучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие.
