Чтобы найти максимальный поток на графике, почему не достаточно насыщать все пути расширения с минимальной емкостью края в этом пути, не учитывая задние края? Я имею в виду, какова точка, называющая ее задним фронтом, если мы предполагаем поток от него?
Почему требуются задние края в алгоритме Форда-Фулкерсона?
Ответ 1
Задние края необходимы при выполнении алгоритма Ford-Fulkerson в случае, если выбранный вами путь не является частью общего потока.
В качестве примера, где нужны задние края, рассмотрите эту сеть потоков:
s
/ \
a b
\ / \
c d
\ /
t
Предположим, что все ребра указывают вниз и что все ребра имеют емкость 1 и что вы хотите найти поток от s до t. Предположим на первой итерации Форда-Фулкерсона, что вы берете путь s → b → c → t. На этом этапе вы нажали одну единицу потока от s до t. Если вы не добавили никаких задних краев, вы останетесь с этим:
s
/
a b
\ \
c d
/
t
Больше нет путей s-t, но это не означает, что у вас максимальный поток. Вы можете нажать две единицы потока от s до t, отправив один по пути s → a → c → t, а другой по пути s → b → d → t. Без каких-либо задних ребер в сети остаточного потока вы никогда не узнаете этот другой путь.
Надеюсь, это поможет!