Каков наиболее эффективный способ пересчета максимального потока на графике, когда:
В первом случае достаточно запустить одну итерацию алгоритма Форда-Фалкерсона? Во втором случае нам нужно пересчитывать максимальный поток только в том случае, если ребро является частью множества ребер максимального потока. Достаточно ли этого для запуска одной итерации Форда-Фалкерсона?
В первом случае "да". По сути, так работает Форд-Фалкерсон. Представьте, что вы запускаете Ford-Fulkerson с нуля на модифицированном графике. Вы могли бы начать с тех же шагов, что и на исходном графике. Чтобы действительно понять, почему это работает, полезно посмотреть, как максимальный поток связан с линейным программированием (см., например, http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/NetFlow/max-flow-lp.html).
Во втором случае ответ в основном «да», если все ваши емкости являются целыми числами. Первое, что вы хотели бы сделать, это изменить ваш старый максимальный поток, чтобы он удовлетворял новым ограничениям. Вы можете сделать это, по сути, найдя путь от источника к приемнику вдоль вашего потока, который проходит через уменьшенное ребро (это несложно сделать, просто начните с уменьшенного края и «следуйте» за потоком). Затем вычтите 1 из вашего потока для каждого ребра на этом пути. Теперь у вас есть поток, который удовлетворяет ограничениям, но может быть неоптимальным. Однако это не более чем на 1 меньше оптимального потока, так что снова будет работать одна итерация Форда-Фалкерсона.
В нецелом случае все может быть сложнее, и в худшем случае вам придется в основном заново решать проблему. Я не знаком с лучшими алгоритмами здесь, но вы можете поискать «динамический максимальный поток». См. также https://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs.
