Изменения

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

Навигация