На этом шаге рассмотрим понятие остаточной сети в методе Форда-Фалкерсона.
Если задана некоторая транспортная сеть G и поток f, то остаточная сеть Gf - это сеть, состоящая из ребер с пропускными способностями, указывающими, как могут меняться потоки через ребра G.
Ребро транспортной сети может пропускать дополнительный поток, равный пропускной способности ребра минус поток, проходящий через это ребро. Если это значение положительно, то переместим такое ребро в Gf с остаточной пропускной способностью cf(u, v) = c(u, v) - f(u, v). Дополнительный поток могут пропустить только те ребра в G, которые входят в Gf; ребра (u, v), поток через которые равен их пропускной способности, имеют cf(u, v) = 0 и не входят в Gf.
Остаточная сеть Gf может включать ребра, не входящие в G. Когда алгоритм работает с потоком с целью его увеличения, ему может потребоваться уменьшиь поток в некотором конкретном ребре. Чтобы представить возможное уменьшение положительного потока f(u, v) в ребре G, поместим ребро (v, u) в Gf с остаточной пропускной способностью cf(v, u) = f(u, v), т.е. ребро, которое может пропустить поток в направлении, обратном к (u, v), не больше потока, идущего по ребру (u, v).
Обратные ребра в остаточной сети позволяют алгоритму пересылать обратно поток, уже переданный по ребру. Пересылка в обратном направлении эквивалентна уменьшению потока в ребре, которое во многих алгоритмах является необходимой операцией.
Представим выше сказанное формально. Пусть есть транспортная сеть G = (V, E) с истоком s и стоком t. Пусть в G имеется поток f, и рассмотрим пару вершин u, v ∈ V. Определим остаточную пропускную способность cf(u, v) как
В силу предположения о том, что из (u, v) ∈ Е выткает (v, u) ∉ Е, в каждой упорядоченной паре вершин применим только один случай из системы.
На следующем шаге рассмотрим понятие увеличивающего пути в методе Форда-Фалкерсона.
