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