Задача о максимальном потоке

 

Теория потоков возникла первоначально в связи с разработкой методов решения задач, связанных с рациональной перевозкой грузов. Схема доставки груза представлялась в виде графа, по ребрам которого проходит подлежащий максимизации поток груза. Позднее обнаружилось, что к задачам о максимальном потоке сводятся и другие важные оптимизационные практические задачи.

1. Стационарный поток. Разрез сети. Пусть – ориентированный граф без петель и без параллельных дуг. Каждой дуге поставлен соответствие вес дуги d_ij – некоторое неотрицательное число, которое назовем пропускной способностью дуги. Среди вершин множества I выделены две вершины: s – источник и t – сток.

Стационарным потоком x величины v на сети назовем совокупность чисел x =, которые удовлетворяют двум условиям:

, (8.1)

\o(I\s\up2( + i - \o(I\s\up2( ( i= (8.2)

 

Здесь + i – множество вершин сети G, соседних справа для вершины i, ( i – множество вершин сети G, соседних слева для вершины i. Число x_ij называется дуговым потоком или потоком по дуге.

Условие (8.1) означает, что дуговой поток является неотрицательным и не должен превышать пропускной способности дуги. Условие вида (8.2) записывается для каждой вершины сети. Для заданного потока величина v является некоторой константой. Левая часть равенства (8.2) для вершины, , означает, что суммарный «вытекающий» из вершины i поток и суммарный «поступающий» в вершину i поток равны. Условие (8.2) называют условием баланса, или условием неразрывности потока.

Пример 1. На сети, представленной на рис. 8.1, первое число, указанное на дуге есть пропускная способность, второе – величина дугового потока. Выяснить, образует ли совокупность дуговых потоков стационарный поток на сети.

 

Проверка условия (8.1). На каждой дуге второе число, т.е. дуговой поток, является неотрицательным и не превосходит первого числа – пропускной способности дуги.

Проверка условия (8.2). Для вершины 2: выходящий поток равен 10 по дуге (2, 5), суммарный входящий поток по дугам (s, 2) и (3, 2) также равен 10. В вершине 3 имеем равенство:

x₃₂ + x₃₅ + x_3t - x_s3 - x₄₃ = 6 + 0 + 10 - 10 - 6 = 0.

Непосредственной проверкой убеждаемся, что в вершинах 4 и 5 также выполняется условие баланса. Для вершин s и t имеем равенства:

x_s2 + x_s3 + x_s4 = 4 + 10 + 16 = 30, - x_3t - x_4t - x_5t = - 10 - 10 - 10 = - 30.

Таким образом, условие (8.2) выполняется для всех вершин. Величина потока равна v = 30.

Пусть I₁ – подмножество I такое, что, . Разрезом на сети G, отделяющим источник s от стока t называется множество таких дуг, что начало каждой из них есть вершина из I₁, а конец – вершина из \.

Согласно определению I₁ I ₁= Æ, I₁ U ₁= I, другими словами, каждая вершина попадает либо в I₁, либо в ₁. Обозначать разрез будем как пару. Рассмотрим сеть на рис. 8.1. Пусть I₁ =,
₁ =. Тогда имеем разрез = {(s, 3), (2, 5), (4, 3), (4, t)}.

Лемма 8.1. Пусть – сеть с источником s и стоком t. Любой ориентированный маршрут (путь) из источника в сток содержит хотя бы одну дугу произвольного разреза.

Доказательство. Пусть s, i₁, i₂, …, i_k, t – последовательность вершин некоторого ориентированного маршрута (пути). – произвольный разрез, отделяющий источник s от стока t. Если вершина i₁Ï I₁, то i₁Î ₁, тогда дуга (s, i₁) – дуга разреза, и лемма доказана. В противном случае для вершины i₂ повторим рассуждения. Если все вершины i₁, i₂, …, i_k попали в I₁, то разрезу принадлежит дуга (i_k, t), поскольку t Î ₁.

Следствие. Пусть – сеть с источником s и стоком t, и – произвольный разрез, отделяющий источник s от стока t. Если из G удалить все дуги разреза, то в новой сети не существует путей из вершины s в вершину t.

Пропускной способностью разреза называется число

d(I₁, ₁) =

Лемма 8.2. Пусть x = – произвольный поток величины v на сети, и (I₁, ₁) – произвольный разрез, отделяющий источник s от стока t. Тогда величина потока не превосходит пропускной способности разреза, т.е.:

v £ d(I₁, ₁). (8.3)

.

Доказательство. Для потока x в любой вершине выполняется условие (8.2). Выберем равенства для вершин множества I₁ и сложим их почленно. Слагаемое x_ij, где iÎ I₁ и jÎ I₁, присутствует в левой части двух равенств: в равенстве для вершины i со знаком «плюс», а в равенстве для вершины j со знаком «минус». При сложении они в сумме дают нуль. Останутся слагаемые x_ij со знаком плюс, если iÎ I₁ и jÎ ₁, и слагаемые x_ij со знаком минус, если iÎ ₁ и jÎ I₁. Значит, получим:

-= v. (8.4)

Поскольку x_ij ³ 0, то

-£ =. (8.5)

Далее в силу того, что x_ij £ d_ij, имеем

£ . (8.6)

Из цепочки равенств и неравенств (8.4)-(8.6) получаем (8.3).

2. Постановка задачи о максимальном потоке. Теорема Форда-Фалкерсона. Задана сеть, в которой выделены две вершины s и t – источник и сток и заданы пропускные способности дуг. Найти поток из вершины s в вершину t максимальной величины. Таким образом, математическая постановка задачи имеет вид:

v ( max,; \I\su(j(\o(I\s\ i (8.7)

Данная задача является задачей линейного программирования. Но применение общих методов решения задач ЛП к задаче (8.7) не рационально, поскольку матрица условий является слабо заполненной. Математиками Фордом (Ford L.R.) и Фалкерсоном (Fulkerson D.R.) был предложен новый способ решения. Он основа на следующей теореме, которая носит имя ее авторов.

Теорема Форда-Фалкерсона. Пусть – сеть с источником s и стоком t. Величина v максимального потока в сети G равна минимальной пропускной способности из всех разрезов, отделяющих источник s от стока t.

Доказательство. Пусть x = – максимальный поток, и его величина равна v. Заметим, что такой поток существует. Почему? Во-первых, в сети G существует, по крайней мере, нулевой поток: с нулевой величиной. Во-вторых, согласно лемме 8.2 величина потока ограничена сверху пропускной способностью любого разреза.

По максимальному потоку построим разрез (I₁, ). Множество I₁ формируем согласно следующим правилам:

а) sÎ I₁ (правило следует из определения разреза);

б) если вершина iÎ I₁ и существует дуга (i, j) Î U, где jÏ I₁ и x_ij < d_ij, то вершину j включаем в множество I₁ (см. рис.8.1);

в) если вершина iÎ I₁ и существует дуга (j, i) Î U, где jÏ I₁ и x_ij > 0, то вершину j включаем в множество I₁ (см. рис. 8.2).

Затем находим множество. Покажем, что tÎ. Предположим противное: tÎ I₁. Тогда среди элементов множества I₁ можно выделить последовательность вершин

s, i₁, i₂, …, i_k, t, (8.8)

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

e = min {e₁, e₂ }, (8.9)

где

e₁ = min { d_ij - x_ij, если (i, j) - прямая дуга в (8.8)},

e₂ = min { x_ij, если (i, j) - обратная дуга в (8.8)}.

Сформируем совокупность чисел =:

=

Очевидно, что для чисел выполняются условия (8.1). Проверим выполнение условий (8.2). Если i = s, и маршрут (8.8) включает дугу, то уравнение имеет вид

\o(I\s\up2( + s -\o(I\s\up2( ( s =\o(I\s\up2( + s + -\o(I\s\up2( ( s =

=\o(I\s\up2( + s + - \o(I\s\up2( ( s = \o(I\s\up2( + s -\o(I\s\up2( ( s + e = v + e,

где + s = + s \ i₁. Аналогичный результат получаем, если маршрут (8.8) включает дугу.

Если i = t, и маршрут (8.8) включает дугу, то уравнение имеет вид

\o(I\s\up2( + t -\o(I\s\up2( ( t - = \o(I\s\up2( + t - \o(I\s\up2( ( t - () =

= \o(I\s\up2( + t - \o(I\s\up2( ( t - e = - v - e,

где ( t =( t \ i_k. Аналогичный результат получаем, если маршрут (8.8) включает дугу.

Для вершин, не входящих в последовательность (8.8), уравнения на совокупности совпадает с уравнением баланса на потоке x. Для любой вершины из множества в уравнении присутствуют ровно два слагаемых, соответствующих дугам маршрута. При этом возможны три различные ситуации: обе дуги выходят из вершины, обе дуги входят в вершину или одна является выходящей, а вторая – входящей (см. рис. 8.3). Непосредственный подсчет показывает, что условия баланса имеют место для любой из этих вершин.

Следовательно, = – поток на сети, величина которого равна, что противоречит максимальности потока x =.

Итак, tÏ I₁, а значит, (I₁, ) – разрез. По построению дуговой поток на дугах разреза насыщенный, т.е. если Î , то. Если дуга такова, что, , то. Поэтому из (8.4) и (8.5) следует

v =-=- 0 = d(I₁, ). (8.10)

Доказано, что величина потока равна пропускной способности построенного разреза.

Осталось показать, что разреза с меньшей пропускной способностью не существует. От противного. Пусть имеется такой разрез (I₂, ), что. Тогда, используя лемму 8.2 и выше доказанное равенство (8.10), имеем

v £ d(I₂, ) < d(I₁, ) = v.

Полученное неравенство v < v говорит, что построенный разрез имеет минимальную пропускную способность. Теорема доказана.

Последовательность (8.8), для которой число e, вычисленное по правилу (8.9), является положительным, называется увеличивающей цепью.

Следствие из теоремы Форда-Фалкерсона. Если в сети построен максимальный поток, то в ней нет увеличивающих цепей.

3. Алгоритм Форда-Фалкерсона. Основная идея алгоритма следует из теоремы Форда-Фалкерсона: чтобы найти максимальный поток, надо построить минимальный разрез (найти на сети узкое место, которое не дает увеличить поток). Считаем, что начальный поток на сети задан, в частности им может быть нулевой поток.

Каждая итерация состоит из двух частей. На первом этапе строится увеличивающий путь (если его построить не удается, то в сети построен максимальный поток), а на втором этапе осуществляется увеличение потока. И первое, и второе реализуется с помощью присвоения вершинам сети специальных меток. В ходе алгоритма вершина может быть в одном из трех состояний: непомеченная (это начальное состояние всех вершин), помеченная, помеченная и просмотренная. Метка вершины содержит информацию о формируемом пути (первая часть метки) и о величине потока, который можно дополнительно пропустить по этому пути из источника до рассматриваемой вершины.

I этап. Все вершины не помечены.

Шаг 1. Вершина s получает метку, что означает, что у вершины s нет предшествующих вершин, и мощность источника неограниченна.

Шаг 2. Пусть имеется некоторое множество помеченных вершин. Произвольно выбираем из них вершину i, и начинаем процесс ее просмотра. Определяем все смежные с ней, но еще непомеченные вершины. Пусть вершина j – одна из них. Вершина j получает метку в двух следующих случаях:

а) если существует дуга, причем, то метка вершины имеет вид. Первая часть метки означает, что вершина j помечена через вершину i, причем дуга является прямой дугой формируемого пути. Вторая часть метки вычисляется по правилу

,

где e_i – вторая часть метки вершины i.

б) если существует дуга, причем, то метка вершины имеет вид. Первая часть метки означает, что вершина j помечена через вершину i, причем дуга является обратной дугой формируемого пути. Вторая часть метки вычисляется по правилу

.

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

При выполнении шага 2 одна вершина становится просмотренной, какие-то вершины становятся помеченными. Поскольку рассматриваемые сети являются конечными, то на шаге 2 возможны два исхода: 1) помечена вершина t; 2) все помеченные вершины просмотрены, но вершина t оказалась непомеченной. В первом случае переходим к II этапу. Во втором – процесс решения закончен, в сети построен максимальный поток. Чтобы найти его величину, найдем пропускную способность разреза, где множество помеченных и просмотренных вершин, – множество непомеченных вершин.

II этап. Строим увеличивающую цепь из вершины s в вершину t. Первая часть метки вершины t указывает вершину i_k, которая в цепи предшествует вершине t. Затем первая часть метки вершины i_k указывает вершину i_k-1, которая предшествует вершине i_k, и так далее, пока первая часть метки некоторой вершины не укажет на вершину s. Выбирается направление в цепи: из вершины s в вершину t. На прямых дугах цепи дуговые потоки увеличиваются на величину e_t, а на обратных дугах уменьшается на эту величину.

Переход к новой итерации.

Пример 2. На сети, представленной на рис. 8.1, найти максимальный поток.

Итерация 1. I этап. Все вершины не помечены.

Шаг 1. Вершина s получает метку.

Шаг 2. Операции этого шага поместим в таблицу:

Просмотр вершины s	Помеченные вершины
Непомеченные смежные: 2, 3, 4	2: [; e2], e2 = min(¥; 12- 4) = 8 3: пометить нельзя, т.к. xs3 = ds3 =10 4: [; e4], e4 = min(¥; 22 - 16) = 6	s: [Æ; ¥ ] 2: [; 8], 4: [; 6],	просмотрена
Просмотр вершины 2	Помеченные вершины
Непомеченные смежные: 3, 5	3: [; e3], e2 = min(8; 6) = 6. 5: пометить нельзя, т.к. x25 = d25 =10.	s: [Æ; ¥ ] 2: [; 8], 4: [; 6], 3: [; 6]	просмотрена просмотрена
Просмотр вершины 4	Помеченные вершины
Непомеченные смежные: t	t: [; et], et = min (6; 16 - 10) = 6.	s: [Æ; ¥ ], 2: [; 8], 4: [; 6], 3: [; 6], t: [; 6]	просмотрена просмотрена просмотрена

II этап. Увеличивающая цепь проходит через вершины s, 4, t. На дугах и дуговые потоки увеличиваем на 6 единиц. Полученный

новый поток указан на рис. 8.4.

Итерация 2. I этап. Все вершины не помечены.

Шаг 1. Вершина s получает метку.

Шаг 2.

 

Просмотр вершины s	Помеченные вершины
Непомеченные смежные: 2, 3, 4	2: [; e2], e2 = min (¥; 12 - 4) = 8 3: пометить нельзя, т.к. xs3 = ds3 =10 4: пометить нельзя, т.к. xs4 = ds4 =22	s: [Æ; ¥ ] 2: [; 8],	просмотрена
Просмотр вершины 2	Помеченные вершины
Непомеченные смежные: 3, 5	3: [; e3], e2 = min (8; 6) = 6. 5: пометить нельзя, т.к. x25 = d25 =10.	s: [Æ; ¥ ] 2: [; 8], 3: [; 6]	просмотрена просмотрена
Просмотр вершины 3	Помеченные вершины
Непомеченные смежные: 4, 5, t	4: [; e4], e4 = min (6; 6) = 6 5: [; e5], e5= min (6; 7 - 0) = 6 t: [; et], et = min (6; 11 - 10) = 1.	s: [Æ; ¥ ] 2: [; 8], 3: [; 6], 4: [; 6], 5: [; 6], t: [; 1]	просмотрена просмотрена просмотрена

II этап. Увеличивающая цепь проходит через вершины s, 2, 3, t. На дугах (s, 2) и (3, t) дуговые потоки увеличиваем на 1 единицу, на дуге (3, 2) дуговой поток уменьшаем. Полученный новый поток указан на рис. 8.5.

Итерация 3. I этап. Все вершины не помечены.

Шаг 1. Вершина s получает метку.

Шаг 2.

 

Просмотр вершины s	Помеченные вершины
Непомеченные смежные: 2, 3, 4	2: [; e2], e2 = min (¥; 12 - 5) = 7 3: пометить нельзя, т.к. xs3 = ds3 =10 4: пометить нельзя, т.к. xs4 = ds4 =22	s: [Æ; ¥ ] 2: [; 7],	просмотрена
Просмотр вершины 2	Помеченные вершины
Непомеченные смежные: 3, 5	3: [; e3], e2 = min (7; 5) = 5. 5: пометить нельзя, т.к. x25 = d25 =10.	s: [Æ; ¥ ] 2: [; 7], 3: [; 5]	просмотрена просмотрена
Просмотр вершины 3	Помеченные вершины
Непомеченные смежные: 4, 5, t	4: [; e4], e4 = min (5; 6) = 5 5: [; e5], e5= min (5; 7 - 0) = 5 t: пометить нельзя, т.к. x3 t = d3 t =11	s: [Æ; ¥ ] 2: [; 7], 3: [; 5], 4: [; 5], 5: [; 5]	просмотрена просмотрена просмотрена
Просмотр вершины 4	Помеченные вершины
Непомеченные смежные: t	t: пометить нельзя, т.к. x4 t = d4t =16	s: [Æ; ¥ ] 2: [; 7], 3: [; 5], 4: [; 5], 5: [; 5],	просмотрена просмотрена просмотрена просмотрена
Просмотр вершины 5	Помеченные вершины
Непомеченные смежные: t	t: [; et], et = min (5; 18 - 10) = 5.	s: [Æ; ¥ ] 2: [; 7], 3: [; 5], 4: [; 5], 5: [; 5], t: [; 5]	просмотрена просмотрена просмотрена просмотрена просмотрена

 

II этап. Увеличивающая цепь проходит через вершины. На дугах, и (5, t) дуговые потоки увеличиваем на 5 единиц, на дуге (3, 2) дуговой поток уменьшаем. Полученный новый поток указан на рис. 29.

Итерация 4. I этап. Все вершины не помечены.

Шаг 1. Вершина s получает метку.

Шаг 2.

 

Просмотр вершины s	Помеченные вершины
Непомеченные смежные: 2, 3, 4	2: [; e2], e2 = min (¥; 12 - 10) = 2 3: пометить нельзя, т.к. xs3 = ds3 =10 4: пометить нельзя, т.к. xs4 = ds4 =22	s: [Æ; ¥ ] 2: [; 2],	просмотрена
Просмотр вершины 2	Помеченные вершины
Непомеченные смежные: 3, 5	3: пометить нельзя, т.к. x32 = 0 5: пометить нельзя, т.к. x25 = d25 =10.	s: [Æ; ¥ ] 2: [; 7]	просмотрена просмотрена

Все помеченные вершины просмотрены. Вершина t не помечена. Поток, указанный на рис. 8.6 является максимальным. Определим его величину. Последней итерации соответствует разрез, где, , (I₁; ) = {, , }. Его пропускная способность равна

d(I₁; ) = 10 + 22 + 10 = 42 = v.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: