Сформулируйте задачу о максимальном потоке как задачу линейного программирования. 27.1-9

Рассмотрим сеть с несколькими веществами (multicommodity flow network) в которой имеются потоки р веществ, для каждого из которых есть свой исток и свой сток. Для каждого вещества есть свой закон сохранения потока, а пропускная способность одна на всех (сумма потоков всех веществ из и в v не должна превышать c(u,v). Для каждого вещества имеется своя величина потока; складывая эти величины, получим суммарную величину (total flow value) потока. Докажите, что поток максимальной суммарной величины можно найти за полиномиальное время, представив эту задачу как задачу линейного программирования. (Любая задача линейного программирования разрешима за полиномиальное время: этот факт мы упоминали в разделе 25.5.)

27.2. Метод Форда-Фалкерсона

В этом разделе мы рассмотрим метод Форда-Фалкерсона отыскания максимального потока. Мы говорим о методе, а не об алгоритме, поскольку есть несколько алгоритмов, его реализующих и отличающихся временем работы. Одна из таких реализаций приведена в конце раздела. Ключевую роль в методе Фода-Фалкерсона играют три понятия: остаточные сети, дополняющие пути и разрезы. Основная теорема - теорема 27.7 о максимальном потоке и минимальном разрезе.

Поиск максимального потока методом Форда-Фалкерсона проводится последовательно. Вначале поток нулевой (и величина его равна нулю). На каждом шаге мы увеличиваем значение потока. Для этого мы находим «дополняющий путь», по которому можно пропустить ещё немного вещества, и используем его для увеличения потока. Этот шаг повторяется, пока есть дополняющие пути. Как покажет теорема о максимальном потоке и минимальном разрезе, полученный поток будет максимальным. Запишем этот план с помощью псевдокода:

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

1положить поток $f$ равным $0$

2while (пока) существует дополняющий путь $р$

3do дополнить $f$ вдоль $р$

4return $f$

Остаточные сети

Пусть дана сеть и поток в ней. Неформально говоря, остаточная сеть состоит из тех рёбер, поток по которым можно увеличить. Строгое определение таково: пусть G = (V, Е) - сеть с истоком s и стоком t. Пусть / - поток в этой сети. Для любой пары вершин и и v. рассмотрим остаточную пропускную способность (residual capacity) из и в v, определяемую как

Она определяет, сколько ещё потока можно направить из и в v. Например, если c(u,v) = 16, a f(u,v) = 11 то мы можем переслать ещё Cf(u,v) = 5 единиц по ребру (и, v). Остаточная пропускная способность Cf (и, v) может превосходить с(и, v), если в данный момент поток f(u, v) отрицателен. Например, если с(и, v) = 16, а f[u,v) = -4, то Cf(u,v) = 20. В самом деле, мы можем увеличить поток на 4, отменив встречный поток, и ещё отправить 16 единиц, не превышая пропускной способности ребра (и, v).

назовём остаточной сетью (residual network) сети G, порождённой потоком /. Её рёбра, называемые остаточными рёбрами (residual edges) допускают положительный поток. На рис. 27.4 (а) изображен поток / в сети G (взятый с рис. 27.1 (Ь)), а на рис. 27.4 (Ь) изображена остаточная сеть Gf.

Заметим, что остаточное ребро (и, v) не обязано быть ребром сети G. Иными словами, может оказаться, что Ef <2 Е. Рёбер (v\, s) и 2,г>з) на рис. 27.4 (Ь) не было в исходной сети. Такое ребро из и в v появляется, когда f(u, v) < 0, то есть когда имеется имеется поток вещества в обратном направлении (по ребру (v,u)) - ведь этот поток можно уменьшить. Таким образом, если ребро (и, v) принадлежит остаточной сети, то хотя бы одно из рёбер (и, v) и (v, и) было в исходной сети. Получаем оценку

Остаточная сеть Gf является сетью с пропускными способностями Cf. Следующая лемма показывает, как соотносятся потоки в исходной и в остаточной сетях.

Лемма 27.2

Пусть G = (V, Е) - сеть с истоком s и стоком t, а / - поток в ней. Пусть Gf - остаточная сеть сети G, порождённая потоком /. Пусть / - поток в Gf. Тогда сумма / + /, определенная как в (27.4), является потоком в сети G величины / + f\ = / + /.

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

(27.5)

Сеть Gf = (V, Ef, где

Ef = {(и, v) е V X V : Cf(u, v) > 0}

Ef\<:2\E\.

Сначала докажем, что / + / будет потоком. Проверим кососимметричность. Для всех и, v £ V выполнено

(f + f)(u,v) = f(u,v) + f(u,v) = = -f(v,u) - f(v,u) = = -(f(v,u) + f(v,u)) = = -(f + f)(v,u).

Проверим условие, связанное с ограниченной пропускной способностью. Заметим, что f(u,v) Cf(u,v) для всех и, v £ V, поэтому

(f + f)(u,v) = f(u,v)+f(u,v) f(u,v) + (c(u,v)-f(u,v)) = c(u,v).

Проверим закон сохранения потока. Для всех и £ V \ {s,t} выполнено равенство (/+ f)(u,V) = f(u,V) + f(u,V) = f(u,V) + f(u, V) =0 + 0 = 0.

Наконец, найдём величину суммарного потока: / + f\ = (/ + f)(s,V) = f(s,V) + f(s,V) = \f\ + \f\.

Дополняющие пути

Пусть / - поток в сети G = (V,E). Назовём дополняющим путём (augmenting path) простой путь из истока s в сток t в остаточной сети Gf. Из определения остаточной сети вытекает, что по всем ребрам (и, v) дополняющего пути можно переслать ещё сколько-то вещества, не превысив пропускную способность ребра.

На рис. 27.4 (Ь) дополняющий путь выделен серым цветом. По нему можно отправить еще 4 единицы потока, так как наименьшая остаточная пропускная способность рёбер этого пути равна c(v2,v3) = 4. Величину наибольшего потока, который можно переслать по дополняющему пути р, назовём остаточной пропускной способностью (residual capacity) пути р:

Cf(p) = mm{cf(u, v) : (и, v) £ р}

Сказанное уточняется в следующей лемме (доказательство мы оставляем читателю в качестве упр. 27.2-3). Лемма 27.3

Пусть / - поток в сети G = (V, Е) и р - дополняющий путь в Gf. Определим функцию fp : V X V -> М. так:

fP(u,v) =

Тогда fp - поток в сети Gf и \fp\ = Cf(p) > 0.

Cf(p), если (и,v) £ р

Cf(p)1 если (и, и) £ р(27.6)

0 в остальных случаях.