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