Сложим л - 1 равенство из условия 3. Имеем

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

Замечание 1. Каждая дуга сети является выходящей и входящей одновременно. Например, дуга AiAk для узла At является выходящей, а для узла Ак входящей.

Замечание 2. И в левой, и в правой части этого равенства потоки суммируются по всем дугам заданной сети. Просто они по-разному сгруппированы.

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

2*4.4) + 2*4.4)+.-.+ 2*4-i>4) =

= 2*4.4)+-+ 2*4.4-1)+ 2*4.4.)

(суммирование в каждом из л слагаемых левой части ведется по всем дугам, выходящим из узлов Д), Ли4-1 соответственно, а суммирование в каждом из л слагаемых правой части ведется по всем дугам, входящим соответственно в узлы Аь Ап). Переписав условие 3 чуть иначе,

2*4.4)= 2*4.4).

к= I, л - 1

(мы поменяли местами левую и правую части и изменили индексы суммирования), нетрудно заметить, что 2-я, 3-я, л - 1-я и л-я суммы в левой части рассматриваемого и весьма большого по размерам равенства соответственно равны 1-й, 2-й, л - 2-й и л - 1-й суммам в его правой части. Это означает, что это равенство легко упрощается до равенства

2*4.4)= 2*4.4)

/€М0}- ми*

(от левой части осталась только 1 -я сумма, а от правой части только л-я). Отсюда уже совсем просто вытекает, что

Рис. 16

1) ориентация всех дуг пути совпадает с направлением перемещения от узла Aq к узлу А (такой путь будем называть ориентированным путем),

2) среди дуг пути есть такие, ориентация которых противоположна направлению, по которому мы перемещаемся из узла Д> в узел Ап; такие дуги в отличие от прямых дуг, ориентация которых совпадает с выбранным направлением перемещения, будем называть обратными.

Путь AoAiAaAs на рис. 16 является ориентированным (ориентация всех дуг пути совпадает с направлением перемещения по этому пути от узла Ао к узлу А5), а путь АоА2А\АуАь - нет (дуга А\А2 для этого пути является обратной). В то же время с направлением перемещения по пути AoAiAiAaAs ориентация дуги АХА2 совпадает (этот путь является ориентированным).

Дугу AjAk сети будем называть насыщенной, если поток по этой дуге равен ее пропускной способности,

tp(AnAk) = c&.

<р(АпАп) = <p(A0,Ai)=v.

Далее будем считать, что в сети нет кратных дуг (дуг, соединяющих одну и ту же упорядоченную пару узлов) и при наличии дуги AtAk дуга АкА{ в сети отсутствует.

Рассмотрим произвольный путь в транспортной сети, ведущей из источника Aq в сток Ап (рис. 16). Возможны два случая:

Поток в сети будем называть полным, если любой ориентированный путь из источника в сток содержит по меньшей мере одну насыщенную ДУГУ-

Покажем, как найти в транспортной сети полный поток.

0-й шаг. Построим произвольный потоку в сети (можно и нулевой).

1-й шаг. Если поток не полный, то в сети существует ориентированный путь, ведущий из источника Д> в сток Ап, ни одна из дуг которого не является насыщенной. Это позволяет увеличить поток по всем дугам этого пути на одно и то же число так, чтобы хотя бы одна из его дуг оказалась насыщенной. Это число легко найти - оно равно

wm(cA-<p(AnAk)\

где минимум берется по всем дугам рассматриваемого пути.

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

Покажем работу предложенного алгоритма на примере конкретной транспортной сети (рис. 17).

Рис. 17

Пример 1.

1-й шаг. Выбираем путь

Наименьшую пропускную способность на этом пути имеет дуга А{Аа - 6 (построенный поток величины 6 показан на рис. 18).