113
правок
Изменения
→Критерий Тарьяна
Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально.
Предположим противное: пусть в остовном дереве остовное дерево <tex> A </tex> все минимальные ребра состоит из всех минимальных ребрах на циклах, тогда оно не минимально.
Попробуем найти цикл в графе <tex> G </tex>, в котором есть ребро <tex> (u, v) \notin A</tex>, и которое легче остальных ребер этого цикла, включая ребро <tex> (a, b) \in A</tex>. Очевидно, что таких пар ребер найти нельзя, так как <tex> A </tex> состоит из ребер наименьшего веса в циклах. Поэтому остовное дерево <tex> A </tex> нельзя улучшить, следовательно оно минимальное {{---}} противоречие.
