Когда можно гарантировать, что ребро не входит в минимальное остовное дерево
При удалении ребер критичен следующий факт, который мы будем называть «свойством цикла».
(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, как и требовалось
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу