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