Эффективно рассчитать максимальный расход после добавления нового ребра в алгоритм Форда Фулкерсона?

Question

Предположим, что максимальный поток для G был вычислен с использованием Ford-Fulkerson, и к E. добавлено новое ребро с единичной емкостью. Каким образом можно эффективно обновить максимальный поток. (t не значение потока, который должен быть обновлен, а сам поток.

Answer 1

Пусть G' - граф с новым ребром e, добавленным в G. Обратите внимание, что мы сохраняем емкость и поток для остальных ребер.

Теперь найдите увеличивающий путь p в G'.

Если p существует, то обновите поток вдоль этого пути в G' на 1. В противном случае поток останется тем же.

Это дает окончательные значения потока. Это правильно, потому что если p существует, то он проходит через e. Следовательно, обновление потока вдоль p ровно на 1. Поскольку алгоритм Фолка-Фулкерсона увеличивает поток на интегральных шагах, пути расширения в G' после этого обновления нет.

Если p не существует, то по аргументу mincut-maxflow это максимальный поток, поскольку mincut равен 0.