На этом шаге рассмотрим понятие увеличивающего пути в методе Форда-Фалкерсона.
Для заданных транспортной сети G = (V, E) и потока f увеливающим путем p является простой путь из s в t в остаточной сети Gf. Согласно оспределению остаточной сети можно увеличить поток в ребре (u, v) увеличивающего пути до cf(v, u) без нарушения ограничения пропускной способности соотвествующего ребра в исходной сети.
Рассмотрим пример транспортной сети (рис. 1):
Рис.1. Пример транспортной сети
Для транспортной сети (рис. 1) существует остаточная сеть Gf с выделенным увеличивающим путем p, его статочная пропускная способность равна cf(p) = cf(v2, v3) = 4 (рис. 2):
Рис.2. Остаточная сеть
Ребра с остаточной пропускной способностью, равной 0, такие как (v1, v3) не показаны.
Поток в G, полученный в результате увеличпесния вдоль пути p на его остаточную пропускную способность представлен на рисунке 3:
Рис.3. Поток после увеличения
Ребра, не несущие поток, такие как (v3, v2), помечены только пропускной способностью.
На рисунке 4 показана останочная сеть, потожденная потоком, представленным на рисунке 3:
Рис.4. Новая остаточная сеть
Путь, выделенный на рисунке 2, является увеличивающим путем. Рассматривая остаточную сеть, представленную на рисунке, как некоторую транспортную сеть, можно увеличивать поток вдоь каждого ребра данного пути до четырех единиц, не нарушая ограничений пропускной способности, поскольку наименьшая остаточная пропускная способность на данном пути составляет cf(v2, v3) = 4.
Максимальная величина, на которую можно увеличить поток в каждом ребре увеличивающего пути p, называется остаточной пропускной способностью пути p и задается формулой:
cf(p) = min{cf(u, v): (u, v) ∈ p}
На следующем шаге рассмотрим понятие разреза транспортной сети.
