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

 

Пусть задан ориентированный граф G=< E, V, H>, в котором направление каждой дуги vÎ V означает направление движения потока (например поток автомобилей), пропускная способность каждой дуги равна d(v). На множестве вершин E выделены две вершины t и s. Вершина t является источником потока, s - стоком. Требуется определить максимальный поток, который может быть пропущен из вершины t в s.

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

0£ x(v) £ d(v), vÎ V. (6. 1)

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

{x(v) |i Î V⁺(i)}= {x(v)| iÎ V ^-(i)}

т.е.

{x(v)| iÎ V⁺(i)} - {x(v)| iÎ V ^-(i)}=0. (6.2)

Для вершины t

{x(v)| iÎ V⁺(i)} -{x(v)¦ iÎ V ^-(i)}=-Q, (6.3)

для вершины s

{x(v)| iÎ V⁺(i)} - {x(v)¦ i Î V ^-(i)}= Q. (6.4)

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

Требуется определить

Q ® max (6.5)

при ограничениях (6.1-6.4).

Величины Q, x(v), vÎ V, удовлетворяющие ограничениям (6.1-6.4) будем называть потоком в сети, и если они максимизируют величину Q, то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vÎ V, являются потоком в сети.

Задача (6.1-6.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tÎ E1, sÎ E2. Разрезом V(E1, E2), разделяющим t и s будем называть множество V(E1, E2)Ì V такое, что для каждой дуги v Î V(E1, E2) либо h1(v)Î E1 и h2(v)Î E2, либо h1(v)Î E2 и h2(v)Î E1.

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

V(E1, E2, +)={vÎ V(E1, E2)| h1(v)Î E1 и h2(v)Î E2}

V(E1, E2, -)= { vÎ V(E1, E2)| h2(v)Î E1 и h1(v)Î E2}

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

Q(E1, E2) =  {x(v)| vÎ V(E1, E2, +)}- {x(v)| vÎ V(E1, E2, -)}

Справедлива следующая

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

В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1, E2) среди всех разрезов V(E1, E2), разделяющих вершины t и s.

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

x(v)=d(v), vÎ V(E1, E2, +),

x(v)=0, vÎ V(E1, E2, -).

 

Пусть Q, x(v), vÎ V, - некоторый поток в сети, последовательность

t=i(0), v(1), i(1), v(2), i(2),..., v(k), i(k)=s,

является цепью, соединяющих вершины t и s. Зададим на этой цепи направление движения от вершины t к s. Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s, и обратной в противном случае. Эту цепь будем называть путем увеличения потока, если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0. По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1, q2), где q1=min (d(v) -x(v)), минимум берется по всем прямым дугам цепи, q1=min (x(v)), минимум берется по всем обратным дугам цепи.

Теорема 2.

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

 

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

вершина i помечена пометкой [g(i), +v(i)], если до нее дошел некоторый дополнительный поток величиной q(i)> 0, а также известна дуга прямая дуга v(i), через которую поступил этот поток, либо помечена пометкой [g(i), -v(i)], если до нее дошел некоторый дополнительный поток величиной q(i)> 0, а также известна обратная дуга v(i), через которую поступил этот поток;

вершина i просмотрена, если помечены все соседние с ней вершины.

Если помечена вершина s, то найден путь увеличения потока величиной q, который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW, в который помещаются номера помеченных вершин в порядке их пометки. С1 - номер в массиве SPW просматриваемой вершины, С2 - номер последней помеченной вершины в этом массиве.