Свойства операций над множествами

     Ниже  показана остаточная сеть для данного  выше потока. Существует ограничивающая пропускная способность для некоторых ребер, тогда как в исходной сети она равна нулю.

     Например, ребро  . Этот поток не максимален. Есть увеличивающие пути , и . Остаточная пропускная способность первого пути

     Увеличивающего  пути не существует в исходной сети, но можно пропустить по нему правильный поток. 

Остаточная  сеть для показанного сверху потока, показывающая остаточные пропускные способности. 

     Самый частый пример использования транспортных сетей — нахождение максимального потока, который означает максимальный суммарный поток от s к t. Для нахождения максимального потока в сети может быть использован алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа и другие. 

     Алгоритм  Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

     Идея  алгоритма заключается в следующем. Изначально величине потока присваивается  значение 0: f(u,v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. 

     Алгоритм  Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE²).

     Алгоритм  Эдмондса — Карпа — это вариант алгоритма Форда — Фалкерсона, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину. 

     В задаче о потоке минимальной стоимости, каждому ребру (u,v) сопоставляется цена k(u,v), цена пересылки потока f(u,v) через ребро . Задача — послать заданное количество потока от s к t с наименьшей ценой.