Совершенно очевидно, что максимальный поток из s в f не может быть больше, чем v (Хт Х^), так как всякая цепь, ведущая из s в г, проходит хотя бы через одну дугу данного разреза. Поэтому достаточно установить существование потока с таким значением. Допустим теперь, что поток задается тп-мерным вектором I, и определим разрез (Хо -> Хо) рекурсивным применением нижеуказанного шага (б).

(а) Начать, полагая Zo-<- { }

(б) Если Xj 6 Хд и, кроме того, < Qa или > О, то включить Xj в множество Хо, и повторять этот шаг до тех пор, пока множество Хо нельзя будет расширять дальше.

Теперь могут возникнуть два случая в зависимости от того, будет ли t Хо или t Хо-

Случай (I), i 6 Хо. В соответствии с шагом (б) отношение t Хо означает следующее: существует такая неориентированная цепь, ведущая из вершины s в вершину t, что для каждой дуги (xi, Xj), используемой цепью в прямом направлении (прямой дуги), \г) < Qij, а для каждой дуги (х^, xi), используемой цепью в обратном направлении, т. е. в направлении от xi к х- (обратной дуги), ftj > 0. (Такая цепь (из дуг), ведущая из s в f, будет называться аугменталъной ) цепью потока.)

Пусть

bf= min [qij - lij] для прямой дуги (xt, Xj), (11.5) бь= min [Iki] для обратной дуги (%, х,), (11.6)

и

6 = min[6y, бь]. (11.7)

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

Используя новый исправленный поток, можно затем повторить шаги (а) и (б) и, определив новый разрез (Хо, Хо), повторить предыдущие рассуждения.

Случай (П), t Хо (т. е. t 6 Хо). В соответствии с шагом (б) ll] = qij для всех (xi, x) 6 (Хо Х ) и li = Oj для всех (ху х^) б

) От augmen {лат.) - увеличение, приращение, прирост.- Прим. перев.

{Хо -*- Хо). Следовательно, и

S 1ы = 0, т. е. величина потока, а именно

(Xi, xj)e(xx) (х^, рес^о^о)

равна величине разреза (Хо-Хд).

Так как в случае (I) поток все время увеличивается по крайней мере на единицу, то при целочисленности всех дц максимальный поток получим за конечное число шагов - как только возникнет случай (II). Этот поток будет равен тогда величине текущего разреза (Хо -Хо), который, следовательно, должен тогда быть равным минимальному разрезу. Теорема доказана.

Конструктивный метод, исиользованный при доказательстве теоремы о максимальном потоке и минимальном разрезе, позволяет сразу же получить алгоритм вычисления максимального потока из данной вершины s в данную вершину t в графе с известными пропускными способностями. Такой алгоритм будет сейчас описан.

Алгоритм начинает работу с произвольного допустимого потока (можно взять и нулевой поток), затем стремятся увеличить величину потока с помощью систематического поиска всех возможных аугментальных цепей потока от s к f. Поиск аугменталь-ной цепи осуществляется с помощью расстановки пометок в вершинах графа. Пометки указывают, вдоль каких дуг может быть увеличен поток и на сколько. Как только найдена одна из таких цепей, поток вдоль нее увеличивают до максимального значения, все пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм заканчивает работу и дает максимальный поток, если нельзя найти ни одну аугментальную цепь. Алгоритм применяется следующим образом.

2.1. Алгоритм расстановки пометок для задачи о максимальном (от s к t) истоке

А. Расстановка пометок. Вершина может находиться в одном из трех состояний: вершине приписана пометка и вершина просмотрена (т. е. она имеет пометку и все смежные с ней вершины

обработаны ), пометка приписана, но вершина не просмотрена (т. е. она имеет пометку, но не все смежные с ней вершины обработаны), вершина не имеет пометки. Пометка произвольной вершины Xi состоит из двух частей и имеет один из двух видов: б) или (-Xj, б). Часть -\-Xj пометки первого типа означает, что поток допускает увеличение вдоль дуги [Xj, Xi). Часть -Xj пометки другого типа означает, что поток может быть уменьшен вдоль дуги {xi, Xj). В обоих случаях б задает максимальную величину дополнительного потока, который может протекать от s к Х; вдоль построенной аугментальной цепи потока. Присвоение пометки вершине xi соответствует нахождению аугментальной цепи потока от S к Xj. Сначала все вершины не имеют пометок.

Шаг 1. Присвоить вершине s пометку (+s, б (s) = схз). Вершине S присвоена пометка и она просмотрена, все остальные вершины без пометок.

Шаг 2. Взять некоторую непросмотренную вершину с пометкой; пусть ее пометка будет (iXft, б (х,)).

(I) Каждой непомеченной вершине Xj 6 Г (xj), для которой tij <Z Qij, присвоить пометку (-Х;, Ь (xj)), где

6(x) = min[6(Xi), qij - lij].

(II) Каждой непомеченной вершине xj Т~ (х), для которой %л > О, присвоить пометку (-Xj, б (х;)), где

6(x) = min[6(xi), Iji] .

(Теперь вершина х; и помечена, и просмотрена, а вершины Xj, пометки которым присвоены в (I) и (II), являются непросмотренными.) Обозначить каким-либо способом, что вершина х^ просмотрена.

Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t будет помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока . Здесь следует отметить, что если - множество помеченных вершин, а Хд - множество не помеченных, то (Хо -> Хд) является минимальным разрезом.

Б. Увеличение потока

Шаг 4. Положить х = t и перейти к шагу 5.

Шаг 5. (I) Если пометка в вершине х имеет вид (+z, б (х)), то изменить поток вдоль дуги (z, х) с % (z, х) на % (z, х) + б {f).

(II) Если пометка в вершине х имеет вид (-z, б (х)), то изменить поток вдоль дуги (х, z) с (х, z) на (х, z) - б (i).