4.5.2 Задача нахождения наибольшего потока в транспортной сети

Постановка задачи:

при заданной конфигурации транспортной сети, когда определены структура графа и пропускные способности дуг, найти наибольшее значение потока,, которое может быть пропущено по данной транспортной сети, и распределение этого потока по дугам транспортной сети.

Дуга называется насыщенной, если поток по этой дуге равен её пропускной способности, т.е. .

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