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

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

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

В этом случае e не принадлежит никакому минимальному остовному дереву графа G.

Доказательство. Пусть T — остовное дерево, содержащее e; необходимо по- казать, что T не обладает минимальной возможной стоимостью. По аналогии с доказательством свойства сечения (4.17) мы воспользуемся методом замены, подставляя на место e ребро с меньшей стоимостью так, чтобы не разрушить остовное дерево.

Итак, мы сталкиваемся с тем же вопросом: как найти ребро с меньшей стои- мостью, которое можно поменять местами с 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} U {e'}. По причинам, изложен- ным при доказательстве свойства сечения (4.17), граф (V, T') является связным и не содержит циклов, поэтому T' является остовным деревом G. Кроме того, посколь- ку e — самое «дорогое» ребро цикла C, а e' принадлежит C, стоимость e' должна быть ниже, чем у e, а следовательно, стоимость T ниже стоимости T, как и требовалось. ■

Рис. 4.11. Замена ребра e ребром e' в остовном дереве T в соответствии с доказательством (4.20)


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Глава 23. Что вас утомляет и что с этим можно сделать.
  2. Мы чувствуем страдание, когда ум верит во что-то, а душа говорит, что это неправда.
  3. Сефера: Крайон, почему, когда Оксане было плохо, я видела саркофаги, мумии и какой-то древнеегипетский ритуал? Что с ней? Что происходит со всеми нами? Расскажи мне, пожалуйста об этом ритуале. Что все это значит?
  4. Что можно получить из пилотажного опроса?
  5. РЕБРО (ПЕРЕЛОМ)
  6. Что можно ожидать от применения BSFF?
  7. Говорят, что люди на внутренней стороне Земли участвуют в создании кругов на полях. Это что - совместный с инопланетянами проект? Станут ли когда-нибудь круги на полях постоянными? Если да, какова будет их роль?
  8. ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ
  9. Что произойдёт, когда сознание будет поднято?
  10. Глава 20 ВРЕМЯ, КОГДА ВЫСМОЖЕТЕ ЧТО-ТООБЪЯСНИТЬ ДРУГИМ
  11. Что происходит, когда мы вбираем в себя негативную энергию
  12. 7. Когда во время разговора она чувствует, что ее третируют
  13. Мы всегда обретаем то, что нам надо, когда перестаем хотеть.