Анализ алгоритмов

Работа всех упомянутых алгоритмов основана на многократной вставке или удале- нии ребер из частичного решения. Итак, чтобы проанализировать их, желательно иметь под рукой базовые факты, определяющие, когда включение ребра в мини- мальное остовное дерево безопасно и, соответственно, когда ребро можно безопас- но удалить на том основании, что оно не может входить в минимальное остовное дерево.
Для данного анализа будет сделано упрощающее предположение, что все

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

Когда же включение ребра в минимальное остовное дерево безопасно? Важ- нейший факт, относящийся к вставке ребра, в дальнейшем будет называться «свойством сечения».

(4.17) Допустим, все стоимости ребер различаются. Пусть S — любое подмно- жество узлов, не пустое и не равное V, и пусть ребро e = (v,w) — ребро минимальной стоимости, один конец которого принадлежит S, а другой — V - S. В этом случае ребро e входит в каждое минимальное остовное дерево.

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

Таким образом, вся суть в том, чтобы найти ребро, которое можно успешно обменять с e. Вспомните, что концами e являются узлы v и w. T — остовное дерево, поэтому в T должен существовать путь из v в w. Предположим, начиная с v, мы последовательно переходим по узлам P; в P существует первый узел w', который принадлежит V- S. Пусть v' S — узел, непосредственно предшествующий w'в P, а e' = (v', w') — соединяющее их ребро. Следовательно, e' — ребро T, один конец ко- торого принадлежит S, а другой — V - S. Ситуация для этой стадии доказательства представлена на рис.

4.10.

Рис. 4.10. Ребро e меняется с ребром e' в остовном дереве T, как описано в доказательстве (4.17)


Заменив e на e', мы получаем множество ребер T = T- {e'} U {e}. Утверждается, что T — остовное дерево. Очевидно, граф (V, T') является связным, поскольку связ- ным является (V, T), а любой путь в (V, T), который использовал ребро e' = (v', w'), теперь может быть «перенаправлен» через ( V, T') для прохождения части P от v' до v, ребра e и затем части P от w до w'. Чтобы понять, что граф (V, T') также является ациклическим, следует заметить, что единственный цикл в (V, T U {e'}) состоит из e и пути P, но этот цикл не присутствует в (V, T') из-за удаления e'.

Ранее было отмечено, что один конец ребра e' принадлежит S, а другой — V- S. Но e является ребром с минимальной стоимостью, обладающим этим свойством, поэтому cг < с'. (Неравенство строгое, потому что никакие два ребра не обладают одинаковой стоимостью.) Следовательно, общая стоимость T меньше общей сто- имости T, как и требуется. ■

Доказательство (4.17) немного сложнее, чем кажется на первый взгляд. Чтобы понять эту сложность, возьмем следующее (более короткое, но неправильное) обо- снование для (4.17). Пусть T — остовное дерево, которое не содержит e. Так как T является остовным деревом, оно должно содержать ребро f один конец которого принадлежит S, а другой — V- S. Так как e является самым «дешевым» ребром, об- ладающим таким свойством, выполняется условие ce < с, а значит, T - {f } U {e} — остовное дерево с меньшей стоимостью, чем у T.

Проблема с этим обоснованием связана не с утверждением о том, что f суще- ствует или что T - {f} U {e} имеет меньшую стоимость, чем T. Проблема в том, что T - {f} U {e} может не быть остовным деревом, как видно на примере ребра f на рис. 4.10. Утверждение (4.17) нельзя доказать простым выбором любого ребра в T, переходящего из S в V - S; необходимо принять меры к тому, чтобы найти правильное ребро.

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

Еще по теме Анализ алгоритмов:

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