двунаправленный максимальный поток с использованием ford-fulkerson

Question

Я думаю, что это похоже на неориентированную графическую версию проблемы максимального расхода.

Итак, для каждого ребра a-> b, b-> a также допустимо. его двунаправленный. И они имеют одинаковую емкость. Это означает, что если у меня есть емкость 10 между двумя вершинами a, b, и у меня есть поток от a до b, который стоит 5, то оставшаяся емкость от a до b будет равна 5, а оставшаяся емкость от b до a.

Мое решение состоит в том, чтобы иметь один направленный край от b до a и другой от a до b. Вопрос: если я уменьшаю остатки от a-> b в остаточном графе, я все же увеличиваю остатки для заднего края b-> a?

Answer 1

Да. В каждом расширенном пути, имеющем доступную емкость, Если вы уменьшаете остаточное значение из a-> b в остаточном графе, вы должны увеличить остаточное значение для заднего края b-> a. Это позволяет потоку позже «возвращаться».