113
правок
Изменения
→Критерий Тарьяна
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.
|proof=
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:.если Если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:
}}
== Уникальность остовного дерева ==
{{Задача
