Остаточный график в максимальном потоке

14

Я читаю о проблеме максимального потока здесь . Я не мог понять интуицию, стоящую за остаточным графиком. Почему мы учитываем задние края при расчете потока?

Может ли кто-нибудь помочь мне понять концепцию остаточного графа?

Как меняется алгоритм в неориентированных графах?

ЦД
источник

Ответы:

28

Интуиция, связанная с остаточным графом в задаче о максимальном потоке, очень хорошо представлена ​​в этой лекции. Объяснение состоит в следующем.

Предположим, что мы пытаемся решить проблему максимального потока для следующей сети (где каждая метка обозначает как поток проталкиваемый через ребро и емкость этого ребра):е е / с е е е е с йGfe/cefeece

Бегущий пример

Один из возможных жадных подходов заключается в следующем:

  1. Выберите произвольный путь расширения который идет от исходной вершины s к стоковой вершине t так , что ePst ); то есть все ребра в P имеют доступную емкость.e(ePfe<ceп
  2. ΔΔпΔзнак равноминеп(се-ее)
  3. Переходите к шагу 1 до тех пор, пока не будет расширенных путей.

То есть найдите путь с доступной емкостью, отправьте поток по этому пути и повторите.

В , одно возможное исполнение выше эвристических находок три пути увеличения , и , в этом порядке. Эти пути перемещают 2, 2 и 1 единицы потока, соответственно, для общего потока 5:P 1 P 2 P 3граммп1п2п3

Возможно выполнение жадного подхода для максимального потока

Выбор путей в этом порядке приводит к оптимальному решению; однако что произойдет, если мы сначала выберем (т. е. перед и )?P 1 P 2п3п1п2

Блокировка пути

Мы получаем то, что называется потоком блокирования : больше не существует путей расширения. В этом случае общий поток равен 3, что не является оптимальным. Эту проблему можно решить, разрешив операции отмены (т. Е. Разрешив отправку потока в обратном порядке, отменив работу предыдущих итераций): просто переместите 2 единицы потока назад от вершины к вершине следующим образом:vвесv

Обратный поток

Кодирование этих разрешенных операций отмены является основной целью остаточного графа .

Остаточный граф сети имеет тот же набор вершин, что и и включает для каждого ребра :G G e = ( u , v ) GRGGe=(u,v)G

  • Передний фронт с емкостью , если .c e - f e c e - f e > 0e=(u,v)cefecefe>0

  • Обратный край с емкостью , если .f e f e > 0e=(v,u)fefe>0

Например, рассмотрим остаточный граф который получается после первой итерации жадной эвристики, когда эвристика сначала выбирает (то есть, когда он получает поток блокировки):P 3RP3

Остаточный график

Обратите внимание, что операция отмены, которая перемещает 2 единицы потока от к , закодирована как прямой (увеличивающий) путь от к в :v s t RwvstR

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

В общем:

Когда расширяющий путь выбран в остаточном графе : RPR

  • Каждое ребро в которое соответствует переднему ребру в увеличивает поток, используя ребро с доступной емкостью. GPG
  • Каждое ребро в которое соответствует ребру, идущему назад в отменяет поток, который был перемещен в прямом направлении в прошлом. GPG

Это основная идея метода Форда-Фулкерсона .

Метод Форда – Фулкерсона действует точно так же, как и описанный выше жадный подход, но останавливается только тогда, когда в остаточном графе больше нет увеличивающих путей (не в исходной сети). Метод корректен (т. Е. Он всегда вычисляет максимальный поток), поскольку остаточный граф устанавливает следующие условия оптимальности :

Для данной сети поток максимален в если в остаточном графе нет пути.f G s - тGfGst

Марио Сервера
источник
Есть ли пример, где пути добавляются в порядке наименьшей длины, как описано в алгоритме Эдмондса-Карпа? В вашем контрпримере первый путь имеет длину 3, в то время как более короткий (то есть 2) путь может быть найден и будет добавлен первым, если мы выполняем Edmonds-Karp.
Рой
Вы можете просто сделать все пути в исходном графе длиной . Для этого разбить вершину на две вершины и . Затем разделите на и . Добавьте также два ребра и с емкостью . Ребро, которое первоначально перешло от к , теперь перейдет от к . Мы можем получить такой же тип блокирующего потока, если сначала выберем путь, содержащий ребро .3 v v 1 v 2 w w 1 w 2 ( v 1 , v 2 ) ( w 1 , w 2 ) 2 v w v 1 w 2 ( v 1 , w 2 )st3vv1v2ww1w2(v1,v2)(w1,w2)2vwv1w2(v1,w2)
Марио Сервера
Ваш пример имеет смысл. Мы всегда можем расширить граф на других ребрах в разрезе, чтобы рассматриваемое ребро находилось на одном из самых коротких путей.
Рой
3

Интуиция за остаточной сетью заключается в том, что она позволяет нам «отменить» уже назначенный поток, т. Е. Если мы уже присвоили 2 единицы потока от до , то передача 1 единицы потока из в интерпретируется как отмена одной единицы исходного потока от к .B B A A BABBAAB

Банах Тарский
источник