Анализ алгоритма: максимальный поток равен минимальному разрезу

Обозначим / поток, возвращаемый алгоритмом Форда-Фалкерсона. Требуется показать, что / имеет максимальную возможную величину среди всех потоков в G; для этого мы воспользуемся методом, упоминавшимся выше: предоставим разрез s-t (A*,B*), для которого v(/) = c(A*,B*).
Тем самым немедленно устанавливается, что / имеет максимальную величину среди всех потоков и что (A*, B”) имеет мини- мальную пропускную способность по всем разрезам s-t.

Алгоритм Форда-Фалкерсона завершается, когда поток f не имеет пути s-t в остаточном графе G. Как выясняется, это единственное свойство, необходимое для доказательства его максимальности.

(7.9) Если f— такой поток s-t, для которого не существует пути s-t в остаточном графе Gf, то в G существует разрез s-t (A*, B*), для которого v(f) = c(A* B*). Соот- ветственно f имеет максимальную величину среди всех потоков в G, а (A* B*) имеет минимальную емкость по всем разрезам s-t в G.

Доказательство. Это утверждение заявляет о существовании разреза, об- ладающего неким желательным свойством; теперь нужно найти такой разрез. Обозначим A* множество всех узлов v в G, для которых в Gf существует путь s-v. Множество всех остальных узлов обозначается B* : B* = V - A*.

Сначала установим, что (A* B”) действительно является разрезом s-t. Безуслов- но, это разбиение V. Источник s принадлежит A*, потому что путь из s в s всегда существует. Кроме того, t ⅜ A* по предположению об отсутствии пути s-t в остаточ- ном графе; следовательно, t B* как и требуется.

Затем предположим, что e = (и, v) является ребром в G, для которого и A*

и v B* как показано на рис. 7.5. Можно утверждать, что f (e) = c Если бы это было не так, то e было бы прямым ребром в остаточном графе Gf, а поскольку и A*, в Gf существует путь s-и; присоединяя e к этому пути, мы получаем путь s-v в Gf, что противоречит предположению о v B*

Рис. 7.5. Разрез (A*,B*) в доказательстве (7.9).


Теперь предположим, что e' = (и', v') является ребром в G, для которого и' B* а v' A*. Можно утверждать, чтоf(e') = 0. Если бы это было не так, то ребро e' по- родило бы обратное ребро e" = (v', и') в остаточном графе G , а поскольку v' A*, в Gf существует путь s-v'; присоединяя e” к этому пути, мы получаем путь s-и' в G , что противоречит предположению о и' B*.

Итак, все ребра из A* полностью насыщены потоком, а все ребра, направленные в A*, совершенно не используются. Теперь мы можем воспользоваться (7.6), чтобы прийти к нужному выводу:

Оглядываясь назад, мы видим, почему два типа остаточных ребер — прямые и обратные — критичны для анализа двух слагаемых в выражении из (7.6).

Так как алгоритм Форда-Фалкерсона завершается при отсутствии пути s-t в остаточном графе, из (7.6) немедленно следует его оптимальность.

(7.10) Поток f возвращаемый алгоритмом Форда-Фалкерсона, является мак- симальным.

Также заметим, что наш алгоритм легко расширяется для вычисления мини- мального разреза s-t (A*,Б*).

(7.11) Для заданного потока f с максимальной величиной разрез s-t с минималь- ной пропускной способностью вычисляется за время O(m).

Доказательство. Просто последуем за построением доказательства (7.9). Мы строим остаточный граф Gf и проводим поиск в ширину или поиск в глубину для определения множества A* всех узлов, доступных из s. После этого мы определяем Б* = V- A* и возвращаем разрез (A* Б*). ■

Обратите внимание: в графе G может быть много разрезов с минимальной про- пускной способностью; процедура в доказательстве (7.11) просто находит один из этих разрезов, начиная с максимального потока f.

Дополнительно анализ алгоритма выявил следующий поразительный факт:

(7.12) В каждой потоковой сети существует поток f и разрез (A, Б), для которых v( f) = c(A, Б).

Суть в том, что f в (7.12) должен быть максимальным потоком s-t; если бы существовал поток f ' с большей величиной, то значение f' превысило бы пропуск- ную способность (A, Б), а это противоречит (7.8). Аналогичным образом можно сделать вывод о том, что (A, Б) в (7.12) является минимальным разрезом (никакой другой разрез не может иметь меньшую пропускную способность), потому что если бы существовал разрез (A', Б') с меньшей пропускной способностью, он был бы меньше величиныf а это снова противоречит (7.8). Из-за этих следствий ут- верждение (7.12) часто называется теоремой о максимальном потоке и минимальном разрезе, и формулируется следующим образом.

(7.13) В любой потоковой сети максимальная величина потока s-t равна мини- мальной пропускной способности разреза s-t.

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

Еще по теме Анализ алгоритма: максимальный поток равен минимальному разрезу:

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