§ 60. Оптимизация потока в сети

Транспортная сеть. Пусть конечный граф без петель, для которого выполняются условия:

3) каждой его дуге приписано значение

Такой граф называют транспортной сетью. называют входом сети, выходом, а с -пропускной способностью дуги и. На рис. 394 изображен граф, являющийся транспортной сетью.

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

где - множество дуг, заходящих в множество дуг, исходящих из

Поток уподобляется количеству вещества, протекающему по дуге.

В силу (60.5) имеем

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

Рис. 394

Например, для сети на рис. 395, если взять

то

— разрез.

Пропускная способность разреза. Число

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

Например, для сети на рис. 395

Так как каждая частица вещества, движущаяся по сети от к пройдет по крайней мере однажды по какой-нибудь дуге из то, каковы бы ни были поток и разрез всегда

Насыщенные дуги. Дугу и называют насыщенной, если

Задача о максимальном потоке. Требуется определить такую функцию что принимает максимальное значение.

Для решения этой задачи нам понадобятся три теоремы. Для простоты записи положим

Теорема Пусть путь, соединяющий вход с выходом

Рис. 395.

Если все дуги этого пути ненасыщенные, то можно увеличить не нарушая соотношения (60.5).

Действительно, рассмотрим разности

и выберем среди них наименьшую Увеличивая на поток в каждой дуге (что не нарушает соотношений (60.4) — (60.6)), приходим к потоку

Пример (рис. 396 и 397). Рассмотрим путь в транспортной сети на рис. 395. Пропускные способности дуг обозначены цифрами в скобках, а пропускные способности потока — цифрами вне скобок. Очевидно, что этот путь не содержит насыщенной дуги. Имеем

Итак, поток на каждой дуге этого пути и, следовательно, поток можно увеличить на единицу.

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

Положим

Теорема II. Если то, увеличивая на поток на каждой дуге и и уменьшая на поток на каждой дуге и цепи мы увеличим поток также на

Цепь, для которой называют насыщенной.

Пример (рис. 398 и 399). Рассмотрим цепь транспортной сети на рис. 398. Имеем

Следовательно, поток можно увеличить на 1. Потоки на дугах таковы:

Поток увеличить нельзя, так как

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

Иначе говоря, нельзя увеличить рассматривая только пути; хотя это иногда можно сделать, рассматривая цепи, соединяющие

(кликните для просмотра скана)

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

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

Очевидно, что А определяет разрез и

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

Из теорем I, II и III вытекает следующая основная теорема.

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

Алгоритм Форда — Фалкерсона [43]. На этих теоремах основан следующий алгоритм для отыскания максимального потока в заданной транспортной сети. Этот алгоритм применим к любой транспортной сети. Для иллюстрации же наших рассуждений, мы ограничимся случаем антисимметрического графа на рис. 400.

1) Отыскание какого-нибудь потока. Строим некоторый поток удовлетворяющий (60.4) — (60.6) (за можно принять и нулевой). На рис. 401 изображен поток для сети на рис. 400.

2) Отыскание полного потока. Если поток не полный, то в сети существует путь от к все дуги которого не насыщены. Отыскиваем такой путь (в частичном графе, образованном ненасыщенными дугами). Увеличивая поток через дуги этого пути до насыщения по крайней мере одной из них, получаем новый поток Если не полный поток, то операция повторяется.

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

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

(кликните для просмотра скана)

(кликните для просмотра скана)

Увеличение на 1 потока, проходящего по этому пути, приводит к насыщению (рис. 404). Наконец, находим путь все дуги которого также не насыщены. Увеличение потока, проходящего по этому пути, приводит к насыщению Получаем рис. 405. Легко видеть, что поток на рис. 405 полный.

3) Отыскание максимального потока Следующий прием, основанный на теореме II, позволяет увеличить полный поток до максимального (если это возможно).

а) Помечаем символом

Рис. 406.

б) Если помеченная вершина, то помечаем символом все непомеченные вершины X, для которых дуги ненасыщенные; помечаем символом все непомеченные вершины X, для которых

в) Если таким способом нам удается пометить выход то это означает, что существует цепь, идущая от к все вершины которой помечены. Вычисляя по формулам (60.17) — (60.20) и полагая (для дуг этой цепи).

мы увеличиваем полный поток на

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

Возвращаясь к примеру (см. рис. 405), помечаем символом символом (для простоты записи — символом символом символом символом символом символом Выписываем цепь Имеем

Уменьшаем на 1 поток через и увеличиваем на 1 потоки через остальные дуги этой цепи (рис. 406). Повторяем процедуру. помечаем символом символом символом символом символом Так как ни одну из оставшихся вершин нельзя пометить, то поток максимален (рис. 406). Подмножеству непомеченных вершин

(рис. 407) отвечает разрез

с пропускной способностью

Рис. 407.

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

Например, нельзя делать так, как это показано на рис. 408; если граф на рис. 408, а свести к графу на рис. 408, в, то допустимый для графа на рис. 408, а поток, представленный на рис. 408, б, нельзя получить, исходя из графа на рис. 408, в.

Отыскание минимального потока. Требуется найти в транспортной сети «поток» наименьшей величины, удовлетворяющий (наряду с условию

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

Опишем алгоритм.

1) Определяем некоторый поток с тем условием, что

2) Уменьшая значения потоков через дуги путей, идущих от к отыскиваем полный поток.

3) Отыскиваем минимальный поток по следующим правилам.

Рис. 408.

а) Помечаем символом

б) Пусть вершина помечена. Помечаем символом любую непомеченную вершину если существует дуга и Помечаем символом любую непомеченную еще вершину если существует дуга

в) Если таким способом удается пометить то можно уменьшить поток через цепь, идущую от до

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

Пример (рис. 409). В качестве исходного выберем поток со значением 74 (рис. 410). Действуя по правилу 2), приходим к полному потоку со значением 39, который изображен на рис. 411. Действуя по 3), замечаем, что поток вдоль цепи можно уменьшить на 2. Увеличивая на 2 поток через дугу и уменьшая на 2 потоки через остальные дуги этой цепи, приходим к рис. 412. Легко проверить, что теперь уже невозможно пометить Получаем минимальный поток со значением 37. Разрез для множества

подтверждает это.

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

(кликните для просмотра скана)

1) Отыскивают такой поток что

2) Полагают

и находят по слегка видоизмененному алгоритму Форда — Фалкерсона такой поток что

Изменение следующее: если — помеченная вершина, то помечают символом любую непомеченную вершину если существует дуга

Рис. 412

Уменьшают поток через дугу даже в том случае, если этот поток нулевой. Допускают также отрицательные потоки, что нарушает условие неотрицательности (60.4). Поток

— искомый минимальный поток.

Пример. Требуется найти такой поток в транспортной сети на рис. 413, что принимает минимальное значение. На рис. 414 определен такой поток что а на рис. 415 указаны пропускные способности Ищем в этой новой транспортной сети некоторый поток такой, что (рис. 416). Затем находим такой максимальный поток что (рис. 417). На рис. 418 изображен минимальный поток в сети на рис. 413 со значением 29. Мы не вводили отрицательных потоков. Дадим другой пример, иллюстрирующий необходимость введенной выше модификации.

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

Рассмотрим на этот раз транспортную сеть на рис. 419. Про водя вычисления, которым отвечают рис. 420—424 (не вводя отрицательных потоков), получаем минимальный поток со значением 35.

Введем теперь отрицательные потоки на сети, изображенной на рис. 419.

Рассматривая цепь изменим потоки с 6 до с 0 до с 15 до с 17 до 26. Рассмотрим теперь цепь можно увеличить поток на 10, допуская отрицательный поток со значением — 10 через дугу Окончательно приходим к минимальному потоку со значением 16 (рис. 425).

Рис. 425. Минимальный поток: 16.

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

и

Другими словами, существует ли поток, насыщающий дуги ? К этому приводят многие комбинаторные задачи (о паросочетании, назначении и т. д.). В частности, интересно получить условия существования потока, насыщающего дуги, инцидентные выходу. Рассмотрим некоторые из них.

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

где

Число называют потребностью вершины Это число можно рассматривать также как верхнюю границу потока через дугу если он существует (в противном случае эта граница равна нулю), как верхнюю границу потоков через дуги

Рис. 426. Все пропускные способности дуг равны 1.

Например (рис. 426), потребность множества равна

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

Теорема Обозначим и рассмотрим подмножество Тогда

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

Пусть минимальный разрез; он определяется некоторым множеством А исходной сети (для которого Согласно (60.36)

откуда

Теорема VI. Условие

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

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

Условие достаточно. Действительно, пусть неравенства (60.39) выполняются. Рассмотрим произвольный разрез определяемый множеством Полагая по теореме V имеем

Отсюда

Следовательно, максимальный поток удовлетворяет условию

т. е. насыщает все дуги, инцидентные

Теорема VII (теорема о насыщении). Условие

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

Доказательство. Это — следствие теоремы VI. Покажем, что условия (60.39) и (60.44) эквивалентны.

1) (60.39) - (60.44), так как в силу теоремы V

откуда, в частности,

2) (60.44) - (60.39), так как, рассматривая множество и полагая имеем

Эта теорема была доказана Гейлом ([8]) (см. также [9]). В следующем параграфе она будет использоваться при изучении свойств паросочетаний простого графа.

Другие задачи о потоке. В некоторых задачах о потоке требуется найти максимальный (или минимальный) поток, удовлетворяющий условию может быть или множеством значений, приписанных дугам, или множеством целых положительных чисел, или множеством интервалов Такого рода задачи можно найти в [8], [9], [43].

УПРАЖНЕНИЯ

(см. скан)

(см. скан)