минимальный вес в разрезе MST

Question

Пусть G - неориентированный граф с различными весами ребер. Пусть T будет MST в G. Пусть (u, v) будет любым ребром в T. Покажите, что есть разрез (S; V-S) такой, что (u; v) является ребром минимального веса в этом разрезе.

Answer 1

Я сделаю это, давайте рассмотрим разрез, такой, что e = (u, v) - единственный из его ребер, принадлежащих T. Предположим, что есть еще один край e 'в разрезе с w (e') w (e), тогда мы могли бы сформировать другой ST, включая e 'и отбрасывая e, который имел бы меньший вес, абсурд.

Answer 2

мы начинаем с | V |режет.Мы объединяем два разреза в каждом цикле.В итоге мы получаем 1 разрез.MST является подмножеством ребер в этом разрезе.Таким образом, для каждого слияния мы выбрали (один из) светлый край (u, v) для этого разреза.Наконец, у нас есть | V | -1 ребра.И наоборот, для каждого края дерева есть вырез, который был «соединен».Итак, если ребро (u, v) находится в MST, то есть разрез (S, VS), соответствующий которому он был светлым ребром.