Предположим, что мы переопределяем остаточную сеть, чтобы запретить ребрам
s. Утверждают, что процедура FORD-FULKERSON по-прежнему корректно вычисляет максимальный поток.
Я думал, что когда мы увеличиваем путь, остаточная пропускная способность обратного ребра увеличивается и может быть использована для уменьшения потока на этом ребре (но в целом для увеличения сетевого потока), если это необходимо. Таким образом, если мы запрещаем ребра в s, это означает, что мы не допускаем уменьшения потока в ребрах s- x (x — это смежный узел с s). Таким образом, в случае, когда мы допускаем ребра в s, у нас может быть такой цикл, как
s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t
Но если мы снова запретим ребра в s, мы сможем найти тот же путь без цикла. Все вышеизложенное — интуитивные идеи, но мне нужно формальное доказательство.
Вопрос взят из Introduction to Algorithms Cormen et al.
