Оптимальность алгоритма обратного удаления

Располагая свойством цикла (4.20), можно легко доказать, что алгоритм обрат- ного удаления строит минимальное остовное дерево. Базовая идея аналогична доказательствам оптимальности двух предыдущих алгоритмов: алгоритм об- ратного удаления добавляет ребро только в том случае, если это оправданно согласно (4.20).

(4.21) Алгоритм обратного удаления строит минимальное остовное дерево графа G.

Доказательство. Рассмотрим любое ребро e = (v, w), удаляемое алгоритмом обратного удаления. На момент удаления e находится в цикле C; и поскольку это первое ребро, обнаруженное алгоритмом в порядке убывания стоимости ребер, оно должно быть ребром с максимальной стоимостью в C. Следовательно, со- гласно (4.20), ребро e не принадлежит никакому минимальному остовному дереву.

Итак, если показать, что результат (V, T) алгоритма обратного удаления являет- ся остовным деревом графа G, дело будет сделано. Очевидно, граф (V, T) является связным, потому что алгоритм не станет удалять ребро, если это приведет к потере связности графа. Действуя от обратного, предположим, что (V, T) содержит цикл C. Рассмотрим ребро e с максимальной стоимостью в C, которое будет первым обна- ружено этим алгоритмом. Это ребро должно быть удалено, потому что его удаление не приведет к потере связности графа, но это противоречит поведению алгоритма обратного удаления. ■

Хотя эта тема далее рассматриваться не будет, сочетание свойства сече- ния (4.17) со свойством цикла (4.20) наводит на мысль, что здесь действует еще более общая закономерность. Любой алгоритм, который строит остовное дерево посредством включения ребер, соответствующих свойству сечения, и удаления ребер, соответствующих свойству цикла (в совершенно произвольном порядке), в конечном итоге сформирует минимальное остовное дерево. Этот принцип по- зволяет разрабатывать естественные жадные алгоритмы для этой задачи, кроме трех уже рассмотренных, и объясняет, почему существует так много жадных алго- ритмов, создающих для нее оптимальные решения.

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

Еще по теме Оптимальность алгоритма обратного удаления:

  1. Упражнение № 3. Удаление обид
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. Оптимальные условия
  9. 2. Специфика и алгоритмы работы с источниками.
  10. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  11. Алгоритм обработки результатов.
  12. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  13. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  14. 6.2.4. Поиск оптимальной финансовой модели СМИ
  15. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  16. 1.1.4. Оптимальная модель социальной сферы современного общества