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

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

Чтобы доказать это, рассмотрим поток с величиной не менее к и построим к путей, непересекающихся по ребрам.

Согласно (7.14) мы знаем, что существует максимальный поток f с целыми величинами потоков. Так как пропускная спо- собность всех ребер ограничивается 1, а поток является целочисленным, каждое ребро, передающее поток в f, имеет ровно одну единицу потока. Следовательно, необходимо доказать следующее.

(7.42) Если f — поток с величиной v, состоящий из 0 и 1, то множество ребер с величиной потока f (e) = 1 содержит множество из ν путей, непересекающихся по ребрам.

Доказательство. Воспользуемся индукцией по количеству ребер в f пере- дающих поток. Если ν = 0, доказывать нечего. В противном случае должно суще- ствовать ребро (s, u), передающее одну единицу потока. Проверим путь из ребер, которые должны передавать поток: так как (s, u) передает единицу потока, из ограничения сохранения потока следует, что должно существовать ребро (v, w), по которому передается единица потока; и т. д. Если продолжать перебор, со вре- менем произойдет одно из двух: либо мы достигнем t, либо узел v будет достигнут во второй раз.

В первом случае мы нашли путь из s в t, и этот путь будет использоваться как один из наших путей v. Обозначим f' поток, полученный уменьшением величины потока на ребрах из P до 0. Новый поток f' имеет величину v - 1, и в нем меньше ребер, передающих поток. Применяя индукционную гипотезу для f , мы получаем v - 1 путей, непересекающихся по ребрам, которые вместе с путем P образуют за- явленные v путей.

Если P достигает узла v во второй раз, значит, ситуация выглядит примерно так, как показано на рис. 7.12. (Все ребра на схеме передают одну единицу потока, а пунктирные ребра обозначают текущий пройденный путь, который только что достиг узла v во второй раз.) В этом случае можно действовать иначе.

Рис. 7.12. Все ребра на схеме передают одну единицу потока. Путь P из пунктирных ребер — один из возможных путей в доказательстве (7.42)


Рассмотрим цикл C из ребер, посещенных между первым и вторым посещени- ем v. Новый поток f' получается из f уменьшением величин потока на ребрах от C до 0. Новый поток f' имеет величину v, но меньшее количество ребер, передающих поток. Применяя индукционную гипотезу к f, мы получаем v путей, непересекаю- щихся по ребрам, как и требовалось. ■

Объединение (7.41) и (7.42) дает следующий результат.

(7.43) В направленном графе G существуют к путей, непересекающихся по ребрам, в том и только в том случае, если величина максимального потока s-t в G не менее к.

Также обратите внимание на то, как доказательство (7.42) предоставляет процедуру построения к путей для заданного целочисленного максимального потока в графе G. Эта процедура иногда называется декомпозицией потока, по- тому что она «раскладывает» поток на множество путей. Соответственно мы показали, что наш алгоритм на базе потока находит максимальное количество путей s-t, непересекающихся по ребрам, а также предоставляет механизм по- строения самих путей.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ