1. Образуем нулевой поток y0, полагая
" u Î U (y0(u) = 0).
2. Преобразуем его в полный поток, повторяя, пока это возможно, следующие действия.
2. 1. Пусть определен поток y i.
2. 2. В N найдем такой путь W, ведущий из I в S, что
" u Î E (W) ((c (u) - y i (u)) > 0).
2. 3. Обозначим как d значение
.
2. 4. Переопределим y i в y i +1по следующей схеме:
y i + 1 (u) = 
Приведенная процедура при каждом выполнении действий 2 делает полностью нагруженным хотя бы одно еще не полностью нагруженное ребро сети. При этом ребра, полностью нагруженные ранее, также остаются полностью нагруженными.
Поэтому приведенная процедура заканчивает свою работу за конечное время. Кроме того, если y i является потоком в сети N, то потоком является и функция y i +1.
Предположим, что заданная процедура заканчивает работу за k шагов. Тогда функция y k образует полный поток в сети N.
Полный поток транспортной сети может быть не максимальным потоком. Например, поток в транспортной сети, приведенной на рис. 6.5, является полным потоком и имеет величину 1.
1 (0)
1 (0)
1 (1) S
I 1(1)
1 (0) 1 (1)
1 (0)
Рис. 6.5
Другой поток в этой же сети, показанные на рис. 6.6, имеет величину 2 и является максимальным.
1 (1)
1 (1)
1 (1) S
I 1(0)
1 (1) 1 (1)
1 (1)
Рис. 6.6
ОПРЕДЕЛЕНИЕ
Множество L Í U называется сечением сети N, если для всякого пути W, ведущего из I в S, выполняется условие
$ u Î E (W)(u Î L).
Если L - сечение транспортной сети N, то после удаления из N ребер множества L сеть распадается на несколько не связанных частей. При этом исток и сток сети попадают в разные части.
Пропускной способностью сечения транспортной сети называется сумма пропускных способностей ребер, входящих в это сечение.
Пропускная способность сечения L обозначаетсякак c (L).
Пропускные способности сечений всякой транспортной сети N и величину произвольного потока y в этой сети связывает следующее соотношение: y(N) 
c (L).
Действительно, суммарный входной поток сети, определяемый как y(N) выходит из I и затем передается по вершинам, связанным с S полностью распределяясь по ребрам из L и затем поступает в стока S. Суммарный поток, прошедший по ребрам L не превосходит пропускной способности сечения и в последующем может поступать в сток сети или повторно проходить по ребрам сечения, входящим в состав циклов сети, по которым течет ненулевой поток. Поэтому y(N) c (L).
Сечения транспортных сетей обладают следующим важным свойством: величина всякого потока в сети не превосходит пропускную способность любого сечения этой сети.
В частности, 
£ 
.
Здесь S - множество всех сечений сети.
ТЕОРЕМА 6.2
Для всякой транспортной сети N = (G, c) с целочисленной функцией c существует максимальный поток.
Доказательство
Пусть N = ((V, U), c) - некоторая транспортная сеть.
Последовательность Н = x 1,..., xk разных вершин этой сети называется цепью, если
" i = 1,..., k - 1 ((xi, xi +1)Î U Ú (xi +1, xi)Î U).
То есть любые две соседние вершины цепи соединяются между собой ребром одним из двух возможных способов. При этом, если (xi, xi +1)Î U, то такое ребро называется прямым. Если же (xi +1, xi)Î U, то такое ребро называется обратным.
Множество всех прямых и обратных ребер цепи Н обозначается как U (H). Множества прямых и обратных ребер той же цепи обозначаются как U+ (H) и U- (H) соответственно.
Построим по шагам поток y в транспортной сети N.
1. Положим i = 0 и методом насыщения дуг построим некоторый полный поток y i в сети N.
2. Пока это возможно, повторяем следующие действия.
2.1. Найдем цепь Н = x 1, x 2,..., xk - 1, x k, где I = x 1 и S = x k,для которой выполняются условия:
" u Î U+ (H) (y i (u) < c (u)); (1)
" u Î U- (H) (y i (u) > 0). (2)
2.2. Если такая цепь H найдена, то вычислим значения:
d 1 = min (c (u)- y i (u)), где u Î U+ (H).
d 2 = min (c (u)), где u Î U- (H).
d = min (d 1, d 2).
(Заметим, что d является целым числом и d > 0.)
2.3. Определим функцию y i+ 1 следующим соотношением:
y(u)+ d, если u Î U+ (H)
y i+ 1(u) = y(u)- d, если u Î U- (H)
y(u), если u Ï U (H).
3. Увеличим значение i на 1.
Действие 2 в приведенной процедуре повторяется конечное число раз, поскольку на всяком шаге величина новой функции y i+ 1 на одном из ребер, ведущих в сток сети, увеличивается на целое число d > 0. Поэтому число повторений выполнения действия 2 не превышает суммы пропускных способностей всех ребер, ведущих в S.
Пусть y k - последняя из функций, определяемых при выполнении приведенной процедуры. Положим y = y k.
Покажем, что y является максимальным потоком в сети N.
1. y является потоком, поскольку если некоторая функция y i - это поток, то действие 2 по потоку y i определяет новый поток y i+ 1.
Действительно, при определении y i+ 1 значения потока изменяются только для ребер из U (H). При этом поток в прямых ребрах возрастает, а в обратных убывает на такую величину, что новое значение для каждого ребра сети не превосходит пропускную способность этого ребра и не становится отрицательным. Поэтому для y i+ 1 выполняется первое условие определения потока в сети.
Для всякой внутренней вершины цепи H сохраняется равенство суммарных входного и выходного потоков.
Действительно, пусть aj - внутренняя вершина из H.
Рассмотрим возможные случаи прохождения ребер из U (H) через вершину aj
1. aj -1 aj a j +1
 |
При этом входящий и выходящий потоки вершины aj увеличиваются на d.
2. aj -1 aj aj +1
 |
В этом случае входящий поток для вершины aj по одному входному ребру возрастает на d, а по другому входному ребру убывает на d, а его величина оказывается неизменной, совпадающей с выходным потоком этой вершины.
aj -1 aj aj +1
3.
Входящий и выходящий потоки для aj уменьшаются на d, оставаясь равными.
aj -1 aj aj +1
4.
Выходящий поток вершины aj по одному ребру возрастает на d, а по другому ребру убывает на d.
Во всех случаях суммарный входящий поток вершины a j для y i + 1 остается равным суммарному выходящему потоку этой вершины, если такое равенство имеет место для y i. Поэтому для y i + 1 выполняется и второе условие определения потока в сети.
2. Покажем, что y является максимальным потоком.
2.1. Обозначим как R - множество таких вершин сети N, что a 
R тогда и только тогда, когда для всякой цепи H, начинающейся в истоке I и заканчивающейся в a, не выполняются условия
" u Î U+ (H) (y i (u) < c (u)) (1)
" u Î U- (H) (y i (u) > 0) (2)
Множество R является непустым, так как из определения функции y следует, что S Î R.
Множество остальных вершин сети обозначим F. Так как для I выполнены условия (1) и (2). Действительно, единственная цепь, ведущая из I в I, состоит из вершины I. Для этой цепи выполняются условия (1) и (2).Значит I F и F не является пустым множеством.
2.2. Обозначим как L множество ребер сети N, начала которых принадлежат множеству F, а концы - множеству R.
Всякий путь W из I в S содержит хотя бы одно ребро из L, поскольку его начало лежит в F, а конец - в R. Следовательно, в последовательности W содержатся две последовательно идущие вершины a и b, для которых a Î F и b Î R. Поэтому L образует сечение сети N.
2.3. Все ребер сечения L справедливо свойство:
" u Î L (y(u) = c (u)).
То есть все ребра L полностью нагружены потоком. В противном случае, если ребро u = (a, b),является недогруженным, то вершина b такого ребра из L, не может принадлежать R.
Действительно, если y(u) < c (u), то найдется цепь, ведущая в b, которая проходит через u, в которой все прямые ребра недогружены, а по обратным ребрам течет ненулевой поток. Такая цепь может быть получена добавлением вершины b к цепи, ведущей в a, для которой выполнены условия (1) и (2). Последнее ребро для такой цепи является прямым и оно недогружено.Поэтому bÎ F, а это противоречит предположению, что bÎ R.
2.4. Если u = (a, b) - это ребро, для которого a R и
b F, то y(u) = 0.
Чтобы убедиться в справедливости последнего свойства, предположим противное: существует такое ребро u = (a, b), что a R, b F иy(u) > 0.
Тогда, так как b F, то существует цепь H = I,..., b, для которой выполнены условия (1) и (2). Но тогда эти же условия выполнены и для цепи H * = I,..., b, a. Поскольку в ней вершины a и b связаны обратным ребром, по которому течет ненулевой поток.
Поэтому a F, что противоречит предположению о том, что a R.
Следовательно, поток между вершинами множеств F и R может протекать лишь в одном направлении.
2.5. Поэтому суммарный поток, проходящий через ребра сечения L, в дальнейшем распространяется только между вершинами множества R и полностью входит в сток S.
Следовательно, справедливо соотношение y(N) = c (L).
То есть y - это максимальный поток, так как его величина совпадает с пропускной способностью сечения L, величину которого не превосходит ни один поток в сети.