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

Страницы работы

Фрагмент текста работы

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

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

Потоком из источника s в сток t (или s-t-потоком) в сети G назовем множество неотрицательных чисел xij, (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 ≤ xij bij , (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 ≤  xij   bij , (i,j)∈ E.(6.3)

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

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

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

–  i X, jX или

–  iX , 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-поток через Fst – это множество неотрицательных чисел {xij}, удовлетворяющих условиям (6.2) и (6.3). 

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

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

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

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

–  помечен;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Конспекты лекций
Размер файла:
259 Kb
Скачали:
0