Когда можно гарантировать, что ребро не входит в минимальное остовное дерево

При удалении ребер критичен следующий факт, который мы будем называть «свойством цикла».

(4.20) Предполагается, что стоимости всех ребер различны. Пусть C — любой цикл в G, а ребро e = (v, w) — ребро с максимальной стоимостью, принадлежащее C. В этом случае e не принадлежит никакому минимальному остовному дереву графа G.

Итак, мы сталкиваемся с тем же вопросом: как найти ребро с меньшей стоимостью, которое можно поменять местами с e? Начнем с удаления e из T; узлы при этом делятся на два подмножества: S, содержащее узел v; и V – S, содержащее узел w.

Теперь один конец ребра, используемого вместо e, должен принадлежать S, а другой — V – S, чтобы снова объединить дерево.

Такое ребро можно найти переходом по циклу C. Ребра C, отличные от e, по определению образуют путь P, один конец которого находится в узле v, а другой в узле w. Если перейти по P от v к w, переход начнется в S и закончится в V − S, поэтому в P существует некоторое ребро e’, соединяющее S с V – S. Ситуация изображена на рис. 4.11.

Теперь рассмотрим множество ребер T’ = T − {e} Ґ {e’}. По причинам, изложенным при доказательстве свойства сечения (4.17), граф (V, T’) является связным и не содержит циклов, поэтому T’ является остовным деревом G.

Кроме того, поскольку e — самое «дорогое» ребро цикла C, а e’ принадлежит C, стоимость e’ должна быть ниже, чем у e, а следовательно, стоимость T’ ниже стоимости T, как и требовалось