Доказательство алгоритма Прима.

[loki122]

Решил реализовать на Python алгоритм Прима. В процессе поиска нужной информации наткнулся на следующее доказательство алгоритма:

Пусть граф G был связным, т. е. ответ существует. Обозначим через T остов, найденный алгоритмом Прима, а через S — минимальный остов. Очевидно, что T действительно является остовом (т. е. поддеревом графа G). Покажем, что веса S и T совпадают. Рассмотрим первый момент времени, когда в T происходило добавление ребра, не входящего в оптимальный остов S. Обозначим это ребро через e, концы его — через a и b, а множество входящих на тот момент в остов вершин — через V (согласно алгоритму, a \in V, b \not\in V, либо наоборот). В оптимальном остове S вершины a и b соединяются каким-то путём P; найдём в этом пути любое ребро g, один конец которого лежит в V, а другой — нет. Поскольку алгоритм Прима выбрал ребро e вместо ребра g, то это значит, что вес ребра g больше либо равен весу ребра e.
Удалим теперь из S ребро g, и добавим ребро e.

Подскажите, как ребро e может не входить в остов S, но при этом ребро g может быть больше или равно ребру е? Сам алгоритм очень простой, но доказательство никак не могу понять.

[Black Fregat]

Что именно непонятно?
Мы ведь изначально предположили, что остовы не совпадают.
Значит, существуют рёбра, не входящие в S, но входящие в T.
Находим певое такое ребро e (по ходу алгоритма Прима).
Показываем, что в S существует ребро g, которое можно выкинуть и заменить на e, не увеличивая суммарный вес остова