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

Пусть задан ориентированный граф G=E,V,H, в котором направление каждой дугиvVозначает направление движения потока (например, поток автомобилей), пропускная способность каждой дуги равнаd_v. На множестве вершинEвыделены две вершиныник. Вершинанявляется источником потока,к– стоком. Требуется определить максимальный поток, который может быть пропущен из вершинынвк.

Обозначим через x_vвеличину потока, движущегося по дугеv. Очевидно, что

0 xv  dv , vV

(7.13)

В каждой вершине iE\{н,к} объем потока входящего равен объему потока выходящего, т.е. справедливо равенство

или
	(7.14)

Соответственно для вершин н ик выполняется

	(7.15)
	(7.16)

Величина Qявляется величиной потока, который выходит из вершиныни входит в вершинук.

Задача. Определить

Q max

(77.5)

при ограничениях (7.13) – (7.16).

Величины (Q, x_v ,vV) удовлетворяющие ограничениям (7.13) – (7.16) будем называть потоком в сети, и если они максимизируют величинуQ, то максимальным потоком. Нетрудно видеть, что значенияQ=0, x_v=0, vV, являются потоком в сети. Задача (7.13) – (7.16) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины Eна две непересекающиеся частиE₁иE₂таким образом, чтобынE₁, кE₂. РазрезомR(E₁,E₂), разделяющимникбудем называть множествоR(E₁,E₂)V такое, что для каждой дугиvR(E₁,E₂) либоh₁(v)E₁ иh₂(v)E₂, либоh₁(v)E₂ иh₂(v)E₁. Так на следующем рисунке множествоE₁={1,4,7}, эти вершины имеют темную заливку.E₂={2,3,5,6,8,9}. РазрезомR(E₁,E₂) являются дуги, через которые прошла пунктирная линия.

Разобьем множество R(E1,E2) на две части следующим образом:

R⁺(E₁,E₂)={vR(E₁,E₂)| h₁(v)E₁ и h₂(v)E₂}

R^–(E₁,E₂)={vR(E₁,E₂)| h₂(v)E₁ и h₁(v)E₂}

Элементы множества R⁺(E₁,E₂) будем называть прямыми дугами, они ведут из множестваE₁, вE₂. Элементы множестваR^–(E₁,E₂) – обратными дугами, они ведут из множестваE₂, вE₁. Потоком через разрез будем называть величину

.

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

.

Очевидно, что 0X(E₁,E₂)D(E₁,E₂).

Справедлива следующая теорема.

Теорема 1. (О максимальном потоке и минимальном разрезе).

В любой сети величина максимального потока Qиз источника нв стоккравна минимальной пропускной способностиD(E₁,E₂) среди всех разрезовR(E₁,E₂), разделяющих вершиныник.

Разрез , на которомQ=, будем называтьограничивающим. На ограничивающем разрезе выполняется

Пусть (Q,x_v,vV) – некоторый поток в сети, и последовательность н=i₀, v₁, i₁ , v₂, i₂,...,v_K, i_K=к, является цепью, соединяющих вершиныник. Зададим на этой цепи направление движения от вершинынкк. Дугаv_jиз этой цепи называется прямой, если ее направление совпадает с направлением движения отнкк, и обратной в противном случае. Эту цепь будем называтьцепью увеличения потока, если для прямых дугvцепи (d_v–x_v)>0 и для обратныхx_v>0. По этой цепи можно пропустить дополнительный потокqизнкквеличинойq=min(q₁,q₂), гдеq₁=min(d_v– x_v), минимум берется по всем прямым дугам цепи, q₂=min(x_v), минимум берется по всем обратным дугам цепи.

Теорема 2. Поток (Q, x_v,vV), максимальный тогда и только тогда, когда не существует пути увеличения потока.

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

Каждой вершине iприпишем пометкуP_i=[g_i,v_i,], гдеg_i– величина дополнительного потока, поступившего в вершинуi,v_i – дуга, по которой поступил поток, – знак «+», если поток поступил по дугеv_i , направленной вi (по прямой дуге; – знак «–», если поток поступил по дугеv_i , направленной отi (по обратной дуге),

Будем говорить, что вершина i

1. Не помечена, если до нее не дошел дополнительный поток. Эта пометка будет иметь вид P_i=[0,–,],

2. Помечена, но не просмотрена, если до нее поток дошел, но не пропущен дальше, пометка будет иметь вид P_i=[g_i,v_i,], гдеg_i>0.

3. Помечена и просмотрена, если до нее поток дошел и пропущен дальше, пометка будет иметь вид .

Алгоритм.

П.0. Для всехvVполагаемx_v=0, полагаем Q=0.

П.1. Все вершины делаем непомеченными. Вершинунделаем помеченной, но не просмотренной с пометкойP_н=[,–,–]. Это означает, что в эту вершину поступает поток неограниченного объема.

П.2. Ищем помеченную, но не просмотренную вершину. Если такой нет, то найденный потокQ,x_v,vV, максимальный и алгоритм заканчивает работу. Если такая вершина нашлась,i– ее номер, то переходим к П.3.

П.3 (просмотр вершиныi).

a) для всехвыполнить:

           положить j=h₂(v),

           если вершина jне помечена и (d_v–x_v)>0, то пометить ее с пометкойP_j=[q,v,+], гдеq=min(q_i, (d_v–x_v)), еслиj=к, то перерейти к П4;

b) для всехвыполнить:

           положить j=h₁(v),

           если вершина jне помечена иx_v>0, то пометить ее с пометкойP_j=[q,v,–], гдеq=min(q_i,  x_v), еслиj=к, то перерейти к П4;

c) пометить вершинуiкак просмотреннуюи перейти к П.2.

П.4(пропуск дополнительного потока).

d) Положитьj=к,q=g_к;

e) Положитьv=v_j ,

     если =«+», то выполнить: {положить x_v=x_v+q,i=h₁(v), еслиi=н, то перейти к П.1, иначе положитьj=iи перейти кe) }

     если =«–», то выполнить: {положить x_v=x_v–q,i=h₂(v), еслиi=н, то перейти к П.1, иначе положитьj=iи перейти кe) }

В результате выполнения этого алгоритма будет получен поток (Q, x_v,vV). Для поиска разреза с минимальной пропускной способностью следует поступить так. На последнем этапе работы алгоритма в П.2 часть вершин будет помечена и просмотрена, эти вершины включим в множество. Разрез будет искомым.

Пример. Для графа, приведенного на следующем рисунке, найти максимальный поток, который будет пропущен из 1–ой вершины в 6–ю. Величины пропускных способностей указаны около дуг.

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

Для этого случая Q=4, потоки по дугам приведены в таблице

Дуга	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10
поток	1	0	3	1	0	2	1	0	1	1

Шаг 1.

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[0,–,]	[0,–,]	[0,–,]	[0,–,]

Шаг 2.Просматриваем вершину 1. Выходящие дугиv₁,v₂,v₃, но только дляv₂(d_v–x_v)>0, поэтом вершина 4 получает пометку [2,v₂,+]. Входящих дуг нет, поэтому дополнительно помеченных вершин нет. Вершина 1 получается помеченной и просмотренной.

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[0,–,]	[2,v2,+]	[0,–,]	[0,–,]

Шаг 3. Помеченная не просмотреная вершина 4, из нее вершина 5 получает пометку [2,v₈,+], и вершина 2 получает пометку [1,v₄, –]. Вершина 4 получается помеченной и просмотренной.

вершина	1	2	3	4	5	6
пометка	[,–,]	[1,v4,-]	[0,–,]	[2,v2,+]	[2,v8,+]	[0,–,]

Шаг 4. Просматриваем вершину 2. Из нее помечается вершина 6, она получает пометку [1,v₆,+].

вершина	1	2	3	4	5	6
пометка	[,–,]	[1,v4,-]	[0,–,]	[2,v2,+]	[2,v8,+]	[1,v6,+]

Эта вершина концевая, поэтому дополнительный поток, который придет в эту вершину q=1. Переходим к восстановлению цепи, по которой может быть пропущен поток и изменению потоков.

Шаг 5 (начало восстановления цепи пропуска дополнительного потока).

Полагаем Q=Q+q=4+1=5.

В вершину 6 дополнительный поток поступил по дуге v₆, направление дуги прямое (смотри пометку этой вершины), поэтому полагаем. Поток поступил из вершиныj=h₁(v₆)=2, переходим к анализу этой вершины.

Шаг 6. В вершину 2 дополнительный поток поступил по дугеv₄, направление дуги обратное (смотри пометку вершины 2), поэтому полагаем. Поток поступил из вершиныj=h₂(v₄)=4, переходим к анализу этой вершины.

Шаг 7. В вершину 4 дополнительный поток поступил по дугеv₂, направление дуги прямое, поэтому полагаем. Поток поступил из вершиныj=h₁(v₂)=1 – начальная вершина, цепь восстановления потока получена, изменения значений потоков вносим в таблицу

Дуга	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10
поток	1	1	3	0	0	3	1	0	1	1

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

Шаг 1.

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[0,–,]	[0,–,]	[0,–,]	[0,–,]

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

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[0,–,]	[1,v2,+]	[0,–,]	[0,–,]

Шаг 3. Просматривая вершину 4 получим

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[0,–,]	[1,v2,+]	[1,v8,+]	[0,–,]

Шаг 4. Просматривая вершину5получим

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[1,v7,–]	[1,v2,+]	[1,v8,+]	[0,–,]

Шаг 4. Просматривая вершину3получим

вершина	1	2	3	4	5	6
пометка	[,–,]	[0,–,]	[1,v7,–]	[1,v2,+]	[1,v8,+]	[0,–,]

Все вершины, которые были помечены, просмотрены, однако вершина 6 не достигнута. Получен максимальный поток.

Ответ:Q=5, значения потоков по дугам приведены в таблице:

Дуга	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10
поток	1	1	3	0	0	3	1	0	1	1

Покажем, как можно получить разрез, на котором максимальный поток совпадает с его пропускной способностью. Вершины, просмотренные на шаге 4 образуют множество E₁={1,3,4,5},E₂=E\E₁={2,6}. Выделим на графе вершины изE₁={1,3,4,5} толщиной окружности и заливкой

Дуги между выделенными и невыдененными вершинами образуют искомый разрез. На графе они также выделены, и по ним проведена пунктирная линия. Из рисунка видно, что дуга v₄разреза обратная, остальные дуги этого разреза прямые. Просчитаем пропускную способность этого разреза и поток по нему . Эти величины совпадают, на прямых дугах поток совпадает с ее пропускной способностью, на обратных дугах поток равен 0.

Рассчитаем пропускную способность некоторого произвольного разреза и поток по нему, например, по разрезу, изображенному на следующем рисунке

D({1,2,3},{4,5,6}=

X({1,2,3},{4,5,6}=,

0X({1,2,3},{4,5,6}D({1,2,3},{4,5,6}. Можно показать (это следует из условия сохранения потока в вершинах), что величина потока не зависит от разреза.