143
правки
Изменения
зяпятушечки
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
Если существует ребро, не максимальное на образовавшемся цикле , мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
Теперь докажем, что дерево, удовлетворяющее условию , минимально:
Обозначим дерево <tex>T</tex>, покажем что его можно построить алгоритмом Крускала.
