Потоки в сетях. Нахождение максимального потока

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

В данном разделе сеть – это связный ориентированный граф G = (V, E) без петель и мультидуг с одним источником s и одним стоком t, в котором каждой дуге (i, j) ∈ E приписана пропускная способность b_ij ≥ 0. 

Потоком из источника s в сток t (или s-t-потоком) в сети G назовем множество неотрицательных чисел x_ij, (i, j)∈E, удовлетворяющих условиям сохранения потока

⎧ −v, ⎪ ∑ ∑xij −       x jk =⎨ 0, i i j:( , )∈E      k:( j k, )∈E            ⎪ v, ⎩

j = s; j ≠ s t, ; j = t

и ограничениям на дуговые потоки

0 ≤ x_ij ≤ b_ij , (i,j)∈E,

где переменная v – общая величина потока.

6.1. Нахождение максимального потока

Задачу нахождения потока максимальной мощности (максимального потока) можно записать в виде

v  = ∑xsj → max; x j s j:( , )∈E                           ⎧−v,     j = s; ⎪

(6.1)

                                     ∑xij − ∑xjk = ⎨0,      j ≠ s t, ;                                  (6.2)

                             i i j:( , )∈E           k:( j k, )∈E ⎪⎩ v,       j = t;

                                          0 ≤  x_ij ≤  b_ij , (i,j)∈ E.(6.3)

С задачей (6.1)–(6.3) связано следующее понятие. 

Определение 6.1. Пусть множества X и X есть разбиение V. Разрезом

(X, X ) сети называется множество дуг {(i, j)∈ E}, для которых:

–  i∈ X, j∈ X или

–  i∈X , j∈ X.

Нас будут интересовать разрезы, разделяющие узлы s и t, которые  на-

зовем s-t-разрезами. Будем предполагать при этом, что s ∈ X, а t ∈X .

Определение 6.2. Пропускной способностью разреза (X, X ) назовем 

величину C X X(             ,  ) = ∑bij .

i X j X∈ ∈,

Очевидно, в общем случае C(X, X ) ≠ C( X, X). 

Заметим, что s-t-разрез  является узким местом сети. Из (6.2) и (6.3) следует, что величина потока v не может превосходить пропускную спо-

собность любого s-t-разреза, т. е. v ≤ C(X, X ), s ∈ X, t ∈X . Справедлива следующая теорема.

Теорема 6.1 (Форда–Фалкерсона). В любой сети величина максимального s-t-потока равна пропускной способности минимального  s-t-разреза.

Обозначим s-t-поток через F_st – это множество неотрицательных чисел {x_ij}, удовлетворяющих условиям (6.2) и (6.3). 

Определение 6.3. Пусть P − некоторый путь, по которому идет положительный поток из источника в сток. Дуга (i, j) ∈ P является прямой дугой пути P, если направление потока в пути совпадает с ее ориентацией. Все другие дуги пути назовем обратными. Будем называть путь из s в t увеличивающим поток F_st, если x_ij < b_ij на всех прямых дугах и x_ji > 0 на всех обратных дугах этого пути. 

Следствие 6.1. Поток F_st максимален только тогда, когда  не существует пути, увеличивающего поток F_st.

Пусть в дальнейшем пропускные способности дуг и, следовательно, величина потока – целые неотрицательные числа. Приведем алгоритм построения максимального потока, который часто называют алгоритмом расстановки пометок Форда–Фалкерсона.

Во время работы алгоритма каждый узел может находится в одном из трех состояний:  – не помечен;

–  помечен;

–  помечен и просмотрен.

Шаг 1 (расстановка пометок). Вначале все узлы не помечены. Метка  узла j состоит из двух частей:

1)  индекса i⁺, если можно увеличить поток из i в j, или индекса i^-, если можно уменьшить обратный поток из j в i;

2)  числа ε(j), указывающего максимальную величину потока, которую можно послать из источника s в j, не нарушая ограничений на пропускные способности.

Сначала источник s получает метку [s⁺,ε(s)=∞]. Теперь вершина s помечена, а все остальные узлы не помечены.

Выберем любой помеченный, но не просмотренный узел j. Пусть он имеет метку [i⁺,ε(j)] или [i⁻,ε(j)]. Каждому непомеченному узлу k, смежному с j, для которого x_jk < b_jk, припишем метку [j⁺,ε(k)], где 

ε(k) = min{ε(j), b_jk − x_jk}. Такие вершины k теперь помечены. Всем смежным с j непомеченным вершинам k, для которых x_kj > 0, припишем метки

[j⁻,ε(k)], где ε(k) = min{ε(j), x_kj}. Такие вершины k теперь также помечены.

Когда все смежные с j узлы получили пометки, вершина j считается помеченой и просмотренной.

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

Если узел t помечен, то на шаге 2 найдется путь, по которому будет увеличен поток.

Шаг 2 (увеличение потока). Если сток t имеет пометку [k⁺,ε(t)], то положим x_kt = x_kt + ε(t). Если t имеет пометку [k⁻,ε(t)], то положим  x_tk = x_tk − ε(t). Перейдем к узлу k.

Если k имеет пометку [j⁺,ε(k)], то положим x_jk = x_jk + ε(t). Если k имеет пометку [j⁻,ε(k)], то положим x_kj = x_kj − ε(t). Переходим к узлу j.

Продолжим этот процесс, пока не достигнем вершины s. Сотрем все пометки и перейдем на шаг 1.

В момент завершения работы алгоритма (на шаге 1) множество поме-

ченных вершин X таково, что дуги (i, j), i ∈ X, j ∈ X насыщены