143
правки
Изменения
фикс
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.
|proof=
[[Файл:GrГраф_тарьян.png|thumb|right|Ребро e имеет максимальный вес на образованном циклеЗеленые ребра принадлежат <tex>T'</tex>, красные принадлежат <tex>T</tex>]]
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
Индукция по количеству ребер в дереве:
'''База: ''' пустое дерево.
'''Переход: '''
Строим дерево <tex>T'</tex> по лемме о безопасном ребре. Рассмотрим минимальное ребро <tex>uv \in T, uv \notin T'</tex>.
