Рис. 27.4 27.4 (а) Поток / в сети G (как на рис. 27.1). (Ь) Остаточная сеть Gf. Выделен дополняющий путь р. Его остаточная пропускная способность с/(р) равна с(г)2,г)з) = 4. (с) Результат добавления потока величины 4, проходящего вдоль пути p. (d) Остаточная сеть, порождённая потоком рис. (с).

Рис. 27.5 27.5 Разрез (S,T) в сети рис. 27.1 (Ь). Здесь S = {s, 1)1,1)2} (черные вершины) и Т = {1)3, v4, t} (белые вершины). При этом f(S, Т) = 19 (поток через разрез) и c(S, Т) = 26 (пропускная способность)

Теперь видно, что если добавить поток fp к потоку /, получится поток в сети G с большим значением. На рис. 27.4 (с) изображён результат добавления потока fp (рис. 27.4 (Ь)) к потоку / (рис. 27.4 (а)). Сформулируем это ещё раз:

Следствие 27.4

Пусть / - поток в сети G = (V, Е), а р - дополняющий путь в сети Gf, заданный равенством (27.6). Тогда функция / = / + fp является потоком в сети G величины / = / + \fp\ > /.

Доказательство

Утверждение вытекает из лемм 27.2 и 27.3. Разрезы в сетях

Метод Форда-Фалкерсона добавляет последовательно потоки по дополняющим путям, пока не получится максимальный поток. Как мы вскоре увидим (теорема о максимальном потоке и минимальном разрезе), величина потока максимальна в том и только в том случае, когда остаточная сеть не содержит дополняющих путей. Для доказательства нам понадобится понятие разреза сети.

Назовём разрезом (cut) сети G = (V, Е) разбиение множества V на две части S и Т = V \ S, для которых s G S и t G Т. (Подобная процедура делалась для минимального покрывающего дерева в главе 24, но теперь граф ориентирован и, кроме того, мы требуем, чтобы s G S, t G Т.) Пропускной способностью разреза (capacity of the cut) (S,T) называют сумму c(S,T). Кроме того, для заданного потока / величина потока через разрез (S, Т) определяется как сумма f(S, Г).

На рис. 27.5 изображён разрез ({s, v\, v2}, {v3, V4, t}) сети рис. 27.1 (b). Поток через этот разрез равен

/К v2) + f(v2, v3) + f(v2, v, 4) = 12 + (-4) + 11 = 19,

а пропускная способность разреза равна

фь v3) + ф2, v4) = 12 + 14 = 26.

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

Следующая лемма утверждает, что величины потоков через все разрезы одинаковы (и равны величине потока).

Лемма 27.5

Пусть / - поток в сети G с истоком s и стоком t, a (S, Т) - разрез сети G. Тогда поток через разрез (S,T) равен f(S,T) = /. Доказательство Многократно используя лемму 27.1, получаем

f(S,T) = f(S,V)-f(S,S) = = f(S,V) =

= f(s,V) + f(S\s,V) = = f(s,V) = = 1/1

Доказанное выше равенство (27.3) (величина потока равна потоку в сток) немедленно следует из этой леммы. Следствие 27.6

Значение любого потока / в сети G меньше или равно пропускной способности любого разреза сети G. Доказательство

Пусть (S, Т) - произвольный разрез сети G. В силу 27.5 и ограничений на потоки по рёбрам

\f\ = f(S,T) = ueSveT

ЕЕс(ии)=

ueSveT = c(S,T).

Теперь докажем основную теорему этого раздела (max-flow min-cut theorem).

Теорема 27.7 (о максимальном потоке и минимальном разрезе) Пусть / - поток в сети G = (V, Е). Тогда следующие утверждения равносильны:

1.Поток / максимален (является потоком максимальной величины) в сети G.

2.Остаточная сеть Gf не содержит дополняющих путей.

3.Для некоторого разреза (S,T) сети G выполнено равенство / = c(S,T). (В этом случае, как показывает следствие 27.6, разрез является минимальным, то есть имеет минимально возможную пропускную способность.)

Доказательство (1) => (2)

Рассуждая от противного, допустим, что поток / максимален, но Gf содержит дополняющий путь р. Рассмотрим сумму / + fp, где fp задается равенством (27.6). По следствию 27.4 эта сумма является потоком в G, величина которого больше /, что противоречит максимальности /.

(2)=» (3)

Пусть в сети Gf нет пути из истока s в сток t. Рассмотрим множество

S = {v G V\ в Gf существует путь из s в v}.

Положим Т = V \ S. Очевидно, что s G S, a t G Г, так как в С/ нет пути из s в t. Поэтому пара (S,T) - разрез. Ни для каких и G S и v G Т ребро (и, v) не принадлежит Ef (в противном случае вершина v попала бы в S). Поэтому f(u, v) = с(и, v). По лемме 27.5 \f\ = f(S,T) = c(S,T).

(3)=> (1)

Для любого разреза (S,T) выполнено / c(S,T) (следствие 27.6). Поэтому из равенства / = c(S,T) следует, что поток / максимален.

Общая схема алгоритма Форда-Фалкерсона

Действуя по методу Форда-Фалкерсона, на каждом шаге мы ви-бираем произвольный дополняющий путь р и увеличиваем поток /, добавляя поток величины Cf(p) по пути р. Приводимый ниже алгоритм использует массив f[u, v] для хранения текущих значения потока. Мы считаем, что функция с(и, v) вычисляется за время 0(1), при этом с(и, v) = 0 если (и, v) Е. (При естественной реализации значение с(и, v) хранится рядом с рёбрами в списках исходящих рёбер.)

В строке 5 величина Cf(u,v) понимается в соответствии с формулой (27.5). Символ Cf(p) обозначает локальную переменную, в которую помещается остаточная пропускная способность пути р.

Ford-Fulkerson($G,s,t$)

1for (для) каждого ребра $(u,v)$ из $E[G]$

2do $f[u,v]\leftarrow 0$

3$f[v,u]\leftarrow 0$

4while (пока) в остаточной сети $G f$ существует путь $р$ из $s$ в $t$

5do $c f(p)\leftarrow\min\{c f(u,v)I(u,v) \textrm{ входит в } p\}$

6for (для) каждого ребра $(u,v)$ пути $p$

7do $f[u,v]\leftarrow f[u,v]+c f(p)$

8$f[v,u]\leftarrow -f[u,v]$

Процедура Ford-Fulkerson следует описанной выше схеме (Ford-Fulkerson-Method). Строки 1-3 задают первоначальное значение потока; цикл в строках 4-8 на каждом шаге находит дополняющий путь р в Gf и увеличивает поток /. Если дополняющего пути нет, найденный поток максимален. Пример работы программы изображен на рис.27.6.