Увеличивающие пути в остаточном графе

На следующем шаге мы формализуем способ проталкивания потока из 5 в t для G. Пусть P является простым путем s-t в g/ — иначе говоря, P не посещает ни один узел более одного раза. Определим критическую пропускную способность bottleneck(P, f) как минимальную остаточную пропускную способность любого ребра P в отношении потока f Затем определим операцию аugment(f P), которая дает новый поток f ' в G.

augmenti/, P)

Присвоить b = bottleneck(P,f)

Для каждого ребра (u, v) e P

Если e= (u, v) является прямым ребром Увеличить f(e) в G на b

Иначе ((u, v) является обратным ребром, присвоить e = (v, и))

Уменьшить f(e) в G на b Конец Если Конец цикла Вернуть (f)

Собственно, остаточный граф определялся исключительно для того, чтобы мы могли выполнить эту операцию. Любой путь s-t в остаточном графе часто называ- ется увеличивающим путем.

Результат аugment(f, P) представляет собой новый поток f' в G, полученный при увеличении и уменьшении величины потока для ребер P. Для начала убедимся в том, что f ' действительно является потоком.

(7.1) f' является потоком в графе G.

Доказательство. Необходимо проверить ограничения пропускной способности и сохранения потока. Так как f' отличается от f только на ребрах P, необходимо про- верить ограничения пропускной способности только на этих ребрах. Итак, пусть (u, v) — ребро P. Неформально ограничение пропускной способности продолжает выполняться, потому что если e = (u, v) является прямым ребром, мы сознательно предотвращаем увеличение потока на e выше с; а если (u, v) является обратным ребром, образовавшимся из ребра e = (v, u)

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

Еще по теме Увеличивающие пути в остаточном графе:

  1. СВОБОДА СЕКСУАЛЬНАЯ ОСТАТОЧНАЯ
  2. 4. От многонациональной империи к остаточному государству: социология в Австрии Национализм, социальные движения и многонациональное государство
  3. Пути оттока
  4. Будьте верны своему пути
  5. Первая глава НА ПУТИ К ЧЕТВЕРТОМУ ИЗМЕРЕНИЮ
  6. Четыре пути к самоуважению
  7. Защита в пути
  8. По пути самосовершенствования
  9. По пути самосовершенствования
  10. Часть первая. Первые шаги на пути к успеху
  11. НА ПУТИ К ЗРЕЛОМУ СОЕДИНЕНИЮ
  12. ЛОВУШКИ НА ПУТИ ПЕРЕМЕН
  13. РЕТРО НА ПУТИ К БУДУЩЕМУ
  14. Тем, кто в Пути