Алгоритм Форда-Фулкерсона на графе с двусторонними ребрами

Question

У меня возникли проблемы с пониманием алгоритма Форда-Фулкерсона для определения максимального потока, и я надеялся на некоторую помощь.

Если мы посмотрим на следующий график с источником A и приемником F, где пропускные способности указаны на каждом ребре.

Вы заметите, что узлы B и C имеют двустороннюю кромку, BC имеют емкость 8, а CB - 3.

Теперь предположим, что первый путь найден - это ABCF, где емкость узкого места равна 8. Таким образом, мы выдвигаем поток 8 на путь, создавая этот график:

Теперь давайтескажем, что следующий путь - ACBDF.

Мой вопрос: какой поток мы теперь можем протолкнуть через CB?Это 11 с использованием 8 из уже выдвинутого потока вместе с емкостью 3 на другом краю, или это только 3 или, возможно, 8?

Спасибо за ваше время.

Answer 1

Я думаю, что вы построили второй остаточный граф неправильно.Вот версия, которую я подготовил из первого графика.

Всякий раз, когда вы пропускаете поток в увеличивающийся путь, вам необходимо отрегулировать пропускную способность вместе с ним.Следовательно, когда вы передали поток со значением 8 по пути ABCF, вам необходимо отрегулировать пропускную способность связанных ребер перед передачей следующего потока в график.

Следовательно, значение 8 получено из емкости узкого места ребра BC или CF.Поскольку вы прошли максимальный поток вдоль этих двух ребер, и вы не можете пройти больше 8, значит, вы максимально использовали пропускную способность этих ребер.Это обобщает идею о том, что всякий раз, когда вы пропускаете некоторый поток, используя некоторые ребра, вам нужно рисовать задние ребра со значениями потока, добавленными с емкостью обратных ребер и вычтенными из передних ребер.

Вы можетеПосмотрите, что из моей версии вашего второго графика.Поскольку у BC больше нет возможности переносить дополнительный поток (8 - 8 = 0), я опустил край и добавил емкость к обратному краю (то есть CB, где емкость была увеличена до 3 + 8 = 11).То же самое произошло и с МВ.

Теперь для AB, так как мы прошли 8 вместе с путем с емкостью 10, у нас еще осталось 2 емкости для прохождения большего потока.Отсюда мы вычитаем значение из AB и получаем (10 - 8 = 2).Мы также добавляем обратный край BA, который создается, добавляя значение потока (то есть 0 + 8 = 8).

Теперь, когда мы правильно построили наш остаточный граф, единственный оставшийся путь расширения, который может переносить поток от AF, - это ABDF со значением потока 2 (пропускная способность узкого места равна 2).

Следовательно, максимальное значение потока (общее значение потока) составляет 8 + 2 = 10

Надеюсь, это поможет!