Расчет максимального потока в сети

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

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

Пусть – поток в сети . Дуга называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если .

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

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

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

Решение задачи о максимальном потоке базируется на теореме Форда и Фалкерсона.

Теорема. (Форд и Фалкерсон). Для любой сети с одним источником и одним стоком максимальная величина потока через сеть равна минимальной из пропускных способностей ее простых сечений.

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

Этап 1. Расчет полного потока

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

Алгоритм.

Шаг 1. Полагаем (т.е. начинаем с нулевого потока). Кроме того, полагаем , где – некоторая рабочая сеть.

Шаг 2. Удаляем из орграфа все дуги, являющиеся насыщенными при данном потоке в сети .

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

Шаг 4. Увеличиваем поток по каждой дуге из на одинаковую величину такую, что, по крайней мере, одна дуга из оказывается насыщенной, а потоки по остальным дугам из не превышают из пропускных способностей. При этом величина потока также увеличивается на , а сам поток остается допустимым. После этого переходим к шагу 2.

Пример. Требуется получить полный поток в сети , приведенной на рис. 3.23а. Начальное состояние этой сети со всеми нулевыми потоками представлено на рисунке 3.23б.

Первая итерация. Выделим в простую цепь и увеличим потоки по дугам из на 3 единицы (до насыщения дуги ). В результате получим поток , содержащий одну насыщенную дугу (см. рис. 3.24а). Пометим ее знаком + и удалим из орграфа . Оставшийся орграф снова обозначаем .

Вторая итерация. Выделим в простую цепь и увеличим потоки по дугам из на две единицы до насыщения дуг и . В результате получим поток , содержащий три насыщенные дуги ( рис. 3.24b). Уберем насыщенные дуги из графа. Оставшийся орграф снова обозначаем . Он представлен на рис. 3.25a.

Третья итерация. Выделим в простую цепь и увеличим потоки по дугам из на две единицы до насыщения дуги . В результате получим поток , содержащий четыре насыщенные дуги (см. рис. 3.25b).

Удалим вновь полученную насыщенную дугу из . Оставшийся орграф снова обозначаем .

Четвертая итерация. Выделим в простую цепь и увеличим потоки по дугам из на две единицы до насыщения дуги . В результате получим поток , содержащий пять насыщенных дуг (см. рис. 3.26b).

В оставшемся орграфе нет прямой цепи от к , соответственно, поток является полным. Величина полученного полного потока равна 9.

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

Этап 2. Расчет максимального потока.

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

На рис. 3.28 приведена сеть, для которой был рассчитан полный поток. В скобках указаны пропускные способности ребер.

Рис. 3.28

В этой сети (орграфе) можно найти цепь , отвечающую указанным требованиям – прямые дуги не насыщены, а обратная дуга насыщена.

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