Каков наиболее эффективный способ пересчета максимального потока на графике, когда:
- мы увеличиваем поток на одном ребре на единицу
- мы уменьшаем поток на одном ребре на единицу
В первом случае достаточно запустить одну итерацию алгоритма Форда-Фалкерсона? Во втором случае нам нужно пересчитывать максимальный поток только в том случае, если ребро является частью множества ребер максимального потока. Достаточно ли этого для запуска одной итерации Форда-Фалкерсона?