Потоки в сетях

Условие 1 – это ограничение по пропускной способности; оно требует, чтобы величина потока по дуге не превышала ее пропускной способности.

Условие 2 – это условие сохранения потока. Для вершин, отличных от s и t, поток, втекающий в вершину, равен потоку, вытекающему из вершины.

В вершинах s и t: из s вытекает поток величины v; в t втекает

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

9.1.2Теорема о максимальном потоке и минимальном разрезе

¹

Лемма 4 Пусть f – поток из s в t в сети. Если (S; S) – разрез, разделяющий s и t, то

¹¹

v = f(S; S) ¡ f(S; S)

До к а з а т е л ь с т в о . Из определения потока f(s; X) ¡ f(X; s) = v,

f(x; X) ¡ f(X; x) = 0; x 6= s; t, f(t; X) ¡ f(X; t) = ¡v.

268 Глава 9. Потоки в сетях

Просуммируем теперь все потоки по x 2 S (помня при этом, что

¹

s 2 S; t 2 S).

v = P [f(x; X) ¡ f(X; x)] = f(S; X) ¡ f(X; S).

x2S

¹

Так как S [ S = X, имеем

¹ ¹

f(S; S [ S) ¡ f(S [ S; S) =

¹¹

=f(S; S) + f(S; S) ¡ f(S; S) ¡ f(S; S) =

¹¹

=f(S; S) ¡ f(S; S). £

Назовем:

дуга (xi; xj) насыщенная,если fij = cij; дуга (xi; xj) ненасыщенная, если fij < cij; дуга (xi; xj) положительная, если fij > 0;

мальный разрез. £ В общем-то мы уже доказали, что величина максимального по-

тока равна минимальному разрезу, но мы еще и покажем как найти такой разрез. Классическое конструктивное доказательство принадлежит Форду и Фалкерсону (книга: Л.Форд, Д.Фалкерсон. Потоки в сетях. – М.,Мир, 1966. – 276 с.).

Теорема 9.1 (Форда – Фалкерсона) (о максимальном потоке и минимальном разрезе).

Для любой сети максимальная величина потока из s в t равна минимальной пропускной способности разреза, разделяющего s и t.

Д о к а з а т е л ь с т в о . В силу леммы и следствий доста-

f(S; S) = c(S; S)

и

¹

f(S; S) = 0.

Итак, пусть f – максимальный поток. Определим S рекуррентно следующим образом:

² включаем s в S: s 2 S;

² если x 2 S и f(x; y) < c(x; y), то включаем y в S: y 2 S;

² если x 2 S и f(x; y) > 0, то включаем y в S: y 2 S.

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

Покажем, что при таком способе включения вершин в множе-

¹

ство S, вершина t в S не попадет, т.е. t 2 S.

Допустим, что это не так ( т.е. t можно включить в S). Тогда из определения S следует, что существует цепь из s в t (это не обязательно ориентированная цепь )

s = x1; x2; : : : ; xl = t,

такая, что для прямых дуг (xi; xi+1)

f(xi; xi+1) < c(xi; xi+1),

а для всех обратных дуг (xi+1; xi) > 0.

(минимум по всем прямым дугам цепи);

±2 = min [f(xi+1; xi)]

xi+1;xi

(минимум по всем обратным дугам цепи);

± = min [±1; ±2].

Изменим теперь поток цепи следующим образом: увеличим поток на всех прямых дугах на величину ±, а на всех обратных дугах уменьшим поток на величину ±.

В результате получится новый допустимый поток, имеющий величину v+±. Добавление ± не приводит к превышению пропускной способности ни по одной дуге, а вычитание не приводит к отрицательным потокам на обратных дугах (по способу выбора ±).

Итак, поток стал v + ±. Но это значит, что поток не был макси-

¹

мальным, и, значит, t 2 S.

¹

Таким образом, (S; S) есть разрез, разделяющий s и t. Кроме того,

¹

f(S; S) = 0. £

9.1.3 Алгоритм Форда – Фалкерсона

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

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

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

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

²вершина помечена и просмотрена (т.е. вершина имеет метку и все смежные с ней вершины “обработаны”);

²вершина помечена, но не просмотрена (т.е. вершина имеет метку, но смежные с ней вершины не “обработаны”);

²вершина не помечена.

Метка некоторой вершины x имеет вид L(x) = [§y; ±(x)]. Часть метки +y означает, что поток может быть увеличен вдоль дуги (x; y). Часть метки ¡y означает, что поток может быть уменьшен вдоль дуги (y; x). В обоих случаях ±(x) показывает максимальную величину, на которую можно увеличить поток от s к x вдоль дополняющей цепи.

Сначала все вершины не имеют меток.

Описание алгоритма.

Шаг 0. Инициализация.

Положим все дуговые потоки равными нулю: fij := 0.

Шаг 1. Назначить вершине s метку L(s) := [+s; ±(s) = 1]. Теперь вершина s помечена, но не просмотрена. Все остальные вершины не помечены.

Шаг 2. Выбрать некоторую помеченную, но не просмотренную вершину xi; пусть ее метка будет [§xk; ±(xi)].

1. Каждой непомеченной вершине xj, смежной с xi (xj 2 ¡xi), для которой fij < cij назначить метку [+xi; ±(xj)], где

±(xj) = min[±(xi); cij ¡ fij].

2. Каждой непомеченной вершине xj 2 ¡¡1xi, для которой fji > 0 назначить метку [¡xi; ±(xj)], где

±(xj) = min[±(xi); fji].

Теперь вершина xi помечена и просмотрена, а вершина xj, метка которой назначена в пунктах 1 или 2, помечена, но не просмотрена. Каким либо образом отмечается, что вершина xi просмотрена.

Шаг 3. Проверка.

Если на шаге 2 какая-либо вершина помечена, то: если помечена вершина t, то на Шаг 4;

если помечена любая другая вершина, то на Шаг 2.

Если на Шаге 2 нельзя назначить никаких меток, то алгоритм заканчивает работу с некоторым максимальным потоком. При этом множество помеченных вершин – это S, а множество непомечен-

¹ ¹

ных вершин – множество S, и (S; S) – минимальный разрез.

Шаг 4. Выбрать вершину x = t; на Шаг 5.

Шаг 5. Увеличение потока.

1.Если метка вершины x имеет вид [+z; ±(x)], то изменить поток вдоль дуги (z; x) с f(z; x) на f(z; x) + ±(t).

2.Если метка вершины x имеет вид [¡z; ±(x)], то изменить поток вдоль дуги (x; z) с f(x; z) на f(x; z) ¡ ±(t).

Шаг 6. Если z = s, то стереть все метки и вернуться к Шагу 1. При этом используется уже увеличенный поток, найденный на Шаге 5.

Если z 6= s, то положить x = z; на Шаг 5.

Пример 9.1. На рисунке приведен пример сети; числа на дугах обозначают их пропускные способности и начальные потоки.

Матрица пропускных способностей имеет следующий вид:

Сначала потоки по всем дугам полагаем равными 0. Расстановка меток по вершинам.

Примечания. 1.Увеличиваем поток по дугам (b; t); (a; b); (s; a) на 2, стираем метки и начинаем новую разметку с учетом увеличившегося потока f(s; a) = 2, f(a; b) = 2; f(b; t) = 2. Потоки по остальным дугам – нулевые.

2. Увеличиваем поток по дугам (b; t); (c; b); (s; c) на 4, стираем метки и начинаем новую разметку с учетом увеличившегося потока:

f(s; c) = 4; f(c; b) = 4; f(b; t) = 6.

3. Увеличиваем поток по дугам (d; t); (c; d); (s; c) на 3, стираем метки и начинаем новую разметку с учетом увеличившегося потока:

f(s; c) = 7; f(c; d) = 3; f(d; t) = 3.

4.Увеличиваем поток по дугам (d; t); (a; d); (s; a) на 2, стираем метки и начинаем новую разметку с учетом увеличившегося потока: f(s; a) = 4; f(a; d) = 2; f(d; t) = 5.

5. Другие вершины пометить не удается. Конец разметки.

¹ ¹

S = fs; a; cg; S = fb; d; tg; (S; S) = (a; b); (a; d); (c; b); (c; d).

¹

v = c(S; S) = 11.

Сеть с распределенными по дугам потоками изображена на рисунке.

J