Потоковые алгоритмы. 
Прикладная математика: технологии применения

Постановка задачи о максимальном потоке. На практике часто встречаются задачи, в которых требуется максимизировать общий объем работ, выполняемых данным комплексом оборудования или минимизировать стоимость перевозки заданного количества груза между некоторыми известными пунктами, или найти максимальную пропускную способность данной сети связи. В этих и целом ряде других задач оперируют понятием потока. Задать поток означает определить объем пересылки (перемещения) некоторых объектов (например, груза, информации,…) из одного пункта, который назовем истоком (s), к другому пункту — стоку (t). Между этими пунктами в общем случае находятся другие промежуточные пункты, соединенные друг с другом некоторыми коммуникациями. Моделью в подобных задачах может выступать сеть.

В потоковых задачах сетью называется граф G (Y, А), каждой дуге которого поставлено в соответствие число с (х, у), называемое пропускной способностью дуги. Количество единиц объектов, проходящих по дуге (х, у), называют потоком в дуге. Будем обозначать поток по этой дуге через ср (х, у). Совокупность потоков в дугах данной сети называют потоком в этой сети.

Построим математическую модель задачи нахождения максимального потока из истока s в сток t. Примем следующие ограничения.

1. Для каждой вершины х Ф s и х Ф t количество единиц потока, входящих в х, равно количеству единиц потока, выходящих из нее. Иначе говоря, во внутренних вершинах сети поток не возникает и не теряется:

2. Поток, проходящий по дуге, не может превышать ее пропускную способность:

3. Исходящий из истока поток должен равняться потоку, входящему в сток:

Поток в сети должен быть максимальным. Формально эта цель может быть записана, например, следующим образом

Задача (16.2)—(16.5) есть задача линейного программирования относительно неизвестных потоков {ф (у, х)} и может быть решена, например, симплексным методом. Однако ввиду обычно высокой размерности этой задачи ее чаще решают в рамках теории графов при помощи реализации так называемых потоковых алгоритмов.

Увеличивающая цепь в сети. Пусть в сети уже существует определенный поток и построен некоторый путь из 5 в t. Можно ли в этом пути увеличить поток, и если возможно, то на сколько? Для ответа на эти вопросы сделаем некоторые построения.

Введем следующие три множества дуг сети, имеющей определенный поток:

• • N — множество дуг, в которых поток не может ни увеличиваться, ни уменьшаться;
• • I — множество дуг, поток в которых может увеличиваться;
• • R — множество дуг, в которых поток может уменьшаться.

Обозначим через t (x_;, Xj) = c (x_i; х_;) — ф (х_;, х-) максимальную величину, на которую поток в дуге (х" х_;) может быть увеличен (для дуг множества I) и через г (х" х.) = ф (х_;, хЛ максимальную величину, на которую поток может быть уменьшен (для дуг множества К). Очевидно, что некоторые дуги для данного состояния сети могут одновременно относиться и к множеству I и к множеству R (будем обозначать это множество /К).

Максимальным увеличением потока в данной цепи назовем величину.

Из этого определения следует, что если 5 = 0, то поток в сети по данному пути не может быть увеличен. В этом случае говорят, что найденная цепь насыщена. Если же величина 8 > 0, то цепь не насыщена и поток из 5 в t может быть увеличен. Если в ненасыщенной цепи поток увеличить на 8, то цепь станет насыщенной.

Пример 16.4.

Для сети, представленной на рис. 16.23, максимальное увеличение потока вычисляется так:

Рис. 16.23. К расчету максимального увеличения потока.

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

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

Шаг 1. Определить для данного состояния графа множества N, I и R. Окрасить вершину s.

Шаг 2. Удалить из дальнейшего рассмотрения дуги, относящиеся к множеству N.

Шаг 3. Находясь в окрашенной вершине, провести окраску смежных неокрашенных дуг и вершин по правилу:

• • если дуга (х, у) е I и является прямой дугой по отношению кх, то окрашиваются вершина у и дуга (х, у), переход к шагу 4;
• • если дуга (у, х) е R и является обратной дугой по отношению к х, то окрашиваются вершина у и дуга (х, у), переход к шагу 4;
• • если из окрашенной вершины нельзя окрасить ни одной вершины, то переход к шагу 5.

Шаг 4. Если окрашена вершина t, то увеличивающая цепь в сети существует. По формуле (16.6) рассчитывают максимальное увеличение потока 5. Задача решена, конец алгоритма.

Шаг 5. Возвращаются к вершине, окрашенной ранее, исключив из дальнейшего рассмотрения ту вершину, из которой попытка окрасить новую вершину была тщетной. Если вернулись не к вершине s, то переход к шагу 3. В противном случае, когда вернулись к исходной вершине, увеличивающий путь в сети отсутствует, конец алгоритма.

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

Пример 16.5.

На рис. 16.24 изображена сеть, для которой требуется определить увеличивающую цепь. Цифры у дуг означают назначенный ранее поток, а цифры в скобках — пропускную способность этих дуг.

Рис. 16.24. Сеть для определения увеличивающей цепи.

Решение. В соответствии с приведенным алгоритмом определим состав множеств N, I, R (рис. 16.25).

Рис. 16.25. Определение множеств N, I, R.

Из вершины s (она окрашена) можем окрасить только вершину а и дугу (s, а). Из вершины, а можно окрасить лишь вершину Ъ (дуга (d, а) обратная и не принадлежит множеству Я). Окрашиваем вершину b и дугу (а, Ь). Из b можем окрасить вершины с, d,/ и соответствующие дуги. Из вершины d нельзя окрасить ни одной вершины, и ее исключаем из дальнейшего рассмотрения. Теперь, например, из/ можно окрасить вершину t. Это означает, что увеличивающая цепь построена. Как показано на рис. 16.26, максимальной увеличивающей является цепь {(s, а), (а, b), (f, t)}. Она обеспечивает увеличение потока на величину 5 = min{6, 3, 5, 4} = 3.

Рис. 16.26. Максимальная увеличивающая цепь.

Алгоритм поиска увеличивающей цепи в чистом виде применяется редко, однако он лежит в основе многих методов решения задач о нахождении потоков.

Алгоритм поиска максимального потока в сети. Идея этого алгоритма чрезвычайно проста. Вначале выбирается начальный допустимый поток из s в t. Такой поток всегда существует — это, например, нулевой поток. Затем применяется процедура поиска увеличивающей цепи. Наличие такой цепи указывает на возможность увеличения начального потока на величину б. Изменяют поток в сети на величину б и вновь ищут увеличивающую цепь. Эта процедура выполняется до тех пор, пока не наталкиваются на невозможность нахождения новой увеличивающей цепи.

Алгоритм поиска максимального потока может быть описан следующим образом.

Шаг1. Выбрать любой возможный начальный поток из вершины 5 в вершину t. Начальным обычно назначают всегда существующий в графе нулевой поток:

Шаг 2. Для данного состояния сети применить алгоритм построения увеличивающей цепи.

Шаг 3. Если такой поток существует, то перейти к шагу 4. В противном случае задача решена: построенный исходящий из вершины s суммарный поток и есть искомый максимальный поток.

конец алгоритма.

Шаг 4. Увеличить существующий поток на найденную величину 8 и перейти к шагу 2.

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

Примечание 16.8. Описанный алгоритм применим к сети с несколькими истоками и стоками. Для этого необходимо ввести один обобщающий сток, в который из каждого реального стока входит дуга с бесконечной пропускной способностью, и один обобщенный исток, из которого с бесконечной пропускной способностью выходят дуги в каждый реальный исток, как это показано на рис. 16.27.

Рис. 16.27. Сеть с обобщающими стоком и истоком.

Пример 16.6.

Для графа, изображенного на рис. 16.28, найти максимальный поток (цифры при дугах означают их пропускные способности).

Решение. Пусть начальный поток нулевой. Поэтому все дуги относятся к множеству/. Применим алгоритм поиска увеличивающей цепи.

Из вершины 5 окрашиваем вершины and. Затем из вершины а можно окрасить вершины b и с. Наконец, из вершины b окрашиваем сток t. Таким образом, получена увеличивающая цепь ((5, а), (а, b), (b, t)), для которой 5 = min{6, 3, 8} = 3.

Рис. 16.28. К поиску максимального потока.

Изменяем значения потока в дугах исходного графа (рис. 16.29) и пересчитываем состав множеств N, I и R. Он оказывается следующим:

• • (s, a) € IR, так как i (s, a) = 3 < 6, одновременно (5, а) е R;
• • (s, d) e I, так как i (s, d) = 0 <8;
• • (a, b) € R, так как r (a, b) = 3 = c (a, b);
• • (b, t) e IR, так как i (b, t) = 3 < 8, одновременно (b, t) e R;
• • остальные дуги принадлежат множеству I.

Рис. 16.29. Первое изменение значений потока в дугах

Вновь применяем алгоритм накопления увеличивающей цепи. Из вершины s окрашиваются вершина а и вершина d. Из вершины а можно окрасить лишь вершину с, затем окрашиваются последовательно вершины е и t. Получается увеличивающая цепь {(s, a), (a, с), (с, е), (е, t)}, позволяющая увеличить поток на 8 = min{3, 3, 4, 5} = 3.

Теперь общий поток составляет 6 ед. Изменим потоки в дугах в соответствии с алгоритмом и отнесем дуги к множествам N, I, R, как показано на рис. 16.30.

Алгоритм построения увеличивающей цепи приводит к получению третьей увеличивающей цепи {(a, d), (d, е), (е, t)} с 8 = min{8, 6, 2} = = 2. Общий поток стал 8 ед. Теперь дуги (s, a), (a, b), (a, c), (a, с) и (e, t) относятся к множеству R, дуга (с, Ь) — к множеству /, а остальные — к множеству IR (рис. 16.31).

Рис. 16.30. Второе изменение значений потока в дугах.

Рис. 16.31. Третье изменение значений потока в дугах.

Применяя алгоритм увеличивающей цепи, последовательно окрашиваем вершину d и из нее вершины сие. Однако из вершины е сток не может быть окрашен, так как прямая по отношению к вершине е дуга (е, 0 принадлежит множеству R. Из вершины с можно окрасить вершину Ь, а из нее — сток t. Найдена увеличивающая цепь {(s, d), (d, с), (с, Ь), (Ь, t)} с 5 = min{6, 4, 7, 5} = 4. Поэтому измененный поток становится равным 12 ед. (рис. 16.32).

Рис. 16.32. Четвертое изменение значений потока в дугах.

Вновь пытаемся найти увеличивающуюся цепь для сети, представленной на рис. 16.32. Дуги (s, а), (а, Ь), (а, с), (d, с) и (е, t) принадлежат только множеству]? (их потоки можно только уменьшить), а остальные дуги одновременно принадлежат к множествам I и R. Согласно алгоритму поиска увеличивающей цепи окрашиваем вершины в следующем порядке. Из истока s вершину d, затем вершину е, из которой можно окрасить вершину с и, наконец, вершины Ъ и t. Получается увеличивающая цепь {(s, d), (d, е), (е, с), (с, b), (b, t)} с 8 = min{2, 2, 1, 3, 1} = 1. Отметим, что поток в обратной дуге (с, е) уменьшается на единицу, однако поток в сети из s в t возрастает (рис. 16.33). Получен общий поток, равный 13 ед., что является конечным результатом, поскольку попытка найти увеличивающую цепь не дает положительных результатов.

Рис. 16.33. Последнее изменение значений потока в дугах.