Постановка задачи о максимальном потоке

На сети с заданными пропускными способностями дуг требуется сформировать максимальный по величине поток между ее истоком и стоком. Этот поток обеспечивается назначением в каждой дуге величины передаваемого ею потока.

Задача о максимальном потоке в сети должна удовлетворять следующим условиям:

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

;

– для вершины , не являющейся стоком или истоком, т.е. , , количество единиц потока, входящего в вершину, должно быть равно количеству единиц потока, выходящего из нее (т.е. требуется сохранение потока):

;

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

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

По определению, поток в сети будет максимальным, если величина этого потока будет больше величины любого другого потока в этой сети.