Оптимальность алгоритмов Крускала и Прима

Теперь мы можем легко доказать оптимальность алгоритмов Крускала и Прима. Оба алгоритма включают ребро только в том случае, когда это включение оправ- дывается свойством сечения (4.17).

(4.18) Алгоритм Крускала строит минимальное остовное дерево графа G.

Доказательство. Рассмотрим любое ребро e = (v, w), добавленное алгоритмом Крускала. Пусть S — множество всех узлов, к которым существует путь из v непо- средственно перед добавлением e. Очевидно, v S, но и w S, так как добавление

e не приводит к созданию цикла.

Более того, никакое ребро из S в V - S еще не было обнаружено, так как любое такое ребро может быть добавлено без создания цикла, а значит, было бы добавле- но алгоритмом Крускала. Следовательно, e — ребро с минимальной стоимостью, у которого один конец принадлежит S, а другой — V - S, и, согласно (4.17), оно принадлежит минимальному остовному дереву.

Итак, если нам удастся показать, что результат (V, T) алгоритма Крускала дей- ствительно является остовным деревом графа G, то дело будет сделано. Очевидно, (V, T) не содержит циклов, поскольку алгоритм проектировался для предотвраще- ния создания циклов. Кроме того, если граф (V, T) не был связным, то существо- вало бы непустое множество узлов S (не равное всему множеству V ), такое, что не существует ребра из S в V- S. Но это противоречит поведению алгоритма: мы знаем, что поскольку граф G является связным, между S и V - S существует как минимум одно ребро, и алгоритм добавит первое из таких ребер при его обнаружении. ■

(4.19) Алгоритм Прима строит минимальное остовное дерево графа G. Доказательство. Для алгоритма Прима также очень легко показать, что он добавляет только ребра, принадлежащие любому возможному минимальному остовному дереву. В самом деле, при каждой итерации алгоритма существует множество S !Ξ V, на базе которого было построено частичное остовное дерево, и добавляется узел v и ребро e, которые минимизируют величину mine=(u vyu^s ce. По определению e является ребром с минимальной стоимостью, у которого один конец принадлежит S, а другой — V - S, поэтому по свойству сечения (4.17) оно присутствует в каждом минимальном остовном дереве.

Также тривиально показывается, что алгоритм Прима строит остовное дерево графа G — а следовательно, он строит минимальное остовное дерево. ■

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

Еще по теме Оптимальность алгоритмов Крускала и Прима:

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