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

Задачи, в которой критерием является поток сети - задача о макс. потоке:

Z ® max; k ¹ t, k ¹ s; 0£ x_ij £ d_ij.

Для нее разработаны алгоритмы, которые эффективнее методов решения транспортных задач. Они работают с сетью как разновидностью графов. Пусть дан ориентированный граф G= (V,U), где V и U - множества вершин и дуг соответственно. Разрез сети на подмножестве вершин A Ì V, A ¹Æ, A ¹ V, tÎ A, sÎ V\A - множество дуг ij Î U таких, что i Î A & j Î V\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза - величина (пропускная способность) разреза:

Пример: Построим один из разрезов сети.

Если A ={t,1,2,3}, то разрезом будет множество дуг P(A)={1,4; 1,6; 2,5; 3,6}, а его величина определяется как d (A)= d₁₄+d₁₆+d₂₅+d₃₆. Дуги, составляющие этот разрез, выделены жирными линиями. Разрез сети, имеющий минимальную пропускную способность - минимальный разрез. Задачи максимизации потока и минимизации величины разреза являются двойственной парой. ->
Теорема Форда и Фалкерсона: Величина потока сети (от истока к стоку) не превосходит пропускной способности минимального разреза и существует макс. поток, величина которого равна пропускной способности минимального разреза.

Методы решения задачи о максимальном потоке основаны на последовательном увеличении потока при соблюдении условий задачи. Аналогом цикла пересчета является увеличивающая цепь - цепь, соединяющая исток и сток, все дуги которой допустимые. Дуга является допустимой увеличивающей, если ее направление совпадает с направлением потока и поток на ней < пропускной способности x_ij<d_ij. Дуга - допустимой уменьшающей, если напр-е дуги противоположно потоку и x_ij >;0.

На увеличивающей дуге поток м возрасти на q_ij=d_ij-x_ij, а на уменьшающей дуге возможно снижение потока, равное q_ij = x_ij. Макс. допустимое изменение величины потока по увеличивающей цепи определяется как минимальное из возможных: q₀ = Макс. поток сети может быть определен по следующему алгоритму.

1. Задать начальную величину потока, обеспечиваемую потоками дуг при выполнении условий задачи - можно взять нулевой поток.

2. Построить увеличивающую цепь. Если это невозможно, решение завершено.

3. Вычислить q₀.

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

Пример: Определить максимальный поток сети. Пропускные способности дуг показаны у стрелок перед косой чертой. Задаем начальный поток. Значения начальных потоков дуг даны за косой чертой, они удовлетворяют условиям задачи. Величина потока сети Z ⁽⁰⁾=7.

Первая итерация. Строим увеличивающую цепь. Она показана на рис. утолщенными линиями. Определяем приращение потока: q₀ = min(7-3, 5-1, 6-4)=2. Увеличиваем потоки дуг цепи на 2 --->

Z ⁽¹⁾= Z ⁽⁰⁾ + q₀ =7+2=9.

Вторая итерация.

Строим увеличивающую цепь {t,1; 1,4; 4,s}. q₀ = min(7-5, 3-2, 5-1)=1.Увеличиваем потоки по дугам цепи на q₀.

<--- Z ⁽²⁾= Z ⁽¹⁾ + q₀ = 9+1=10.

Третья итерация.

Новая цепь состоит из увеличивающих дуг t,3 и 4,s и уменьшающей дуги 4,3. q₀ = min(4-2, 1, 5-2)=1. Изменяем потоки: на дугах t,3 и 4,s увеличиваем, а на дуге 4,3 уменьшаем на величину q₀. --->

Тогда получаем Z ⁽³⁾= Z ⁽²⁾ + q₀ = 10+1=11.

Так как увеличивающую цепь построить нельзя, последнее решение является оптимальным. Максимальный поток сети равен 11.

Минимальный разрез рассмотренной сети соответствует множеству вершин А ={t,1,2,3,5,6}, то есть P(A)={1,4; 5,s; 6,s}. Его пропускная способность d (A)= d₁₄+d_5s+d_6s =3+2+6=11 равна величине максимального потока, что согласно теореме Форда-Фалкерсона также является признаком оптимальности найденного решения.