143
правки
Изменения
м
исправлен ляп
Теорема Тарьяна (критерий минимальности остовного дерева)
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро не из графа дерева является максимальным на цмкле, который образуется при его добавлении в дерево
|proof=
Если существует ребро, не максимальное на образовавшемся цикле мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
