Изменения
Нет описания правки
Теперь докажем, что дерево <tex>T</tex>, удовлетворяющее условию, минимально:
Для этого заметимпокажем, что для любого разреза <tex>\langle S, T \rangle</tex> исходного графа <tex>G</tex>, вес ребра <tex>uv \in T</tex>, пересекающего этот разрез, минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим ребро <tex>ab \notin T</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>T</tex>.
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) </tex>, ч. т. д.
