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

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

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

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

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

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

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

1. Выберите произвольный путь расширения который идет от исходной вершины s к стоковой вершине t так , что ∀ $P$$s$$t$ ); то есть все ребра в P имеют доступную емкость.$\forall e \: (e \in P \rightarrow f_e \lt c_e$$P$
2. $\Delta$$\Delta$$P$$\Delta=\min_{e \in P} (c_e-f_e)$
3. Переходите к шагу 1 до тех пор, пока не будет расширенных путей.

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

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

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

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

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

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

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

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

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

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

В общем:

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

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

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

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

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

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