7.6. Потоки с ограничениями на дугах

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

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

1. При каких условиях в данной сети с ограниченными пропускными способностями существует допустимый поток

2. Если допустимый поток существует, то каковы его характеристики?

3. Если существуют допустимые потоки из и в имеющие величину то как найти конкретный поток такого типа?

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

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

Обозначим через X дополнение к X относительно Напоминая терминологию, относящуюся к разрезам, укажем, что если оба непусты, то и являются двумя ориентированными разрезами, соответствующими разбиению вершин

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

Доказательство. Так как для всех остальных то мы имеем

откуда после упрощения получим

Так как по условию допустимый поток, то соотношение

выполняется для любой Подставляя эти границы в выражение для получаем требуемые неравенства.

Отметим, что было выбрано произвольно, за исключением условия и Если мы определим

и

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

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

С другой стороны, взяв имеем

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

Упражнение 7.6. (см. скан)

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

Рис. 7.7.

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

Теорема 7.4. Пусть допустимый поток из имеющий величину Если существует допустимый поток имеющий величину то существует простых потоков по цепям

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

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

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

Упражнение 7.7. (см. скан)

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

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

потоков по цепям является не только теоретическим приемом, но и практическим методом. Перед тем как дать точное описание этого процесса, проиллюстрируем его основные особенности неформально, используя в качестве примера транспортную сеть, изображенную на рис. 7.8. Числа на рис. 7.8, а показывают пропускные способности дуг, источник и сток соответственно.

Рис. 7.8.

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

Наша цель — максимизировать поток из у в Очевидно, что максимальная величина не может быть больше 5 из-за пропускных способностей дуг, инцидентных вершине В начале возьмем любой путь, соединяющий например, путь, определенный следующей последовательностью вершин и, и припишем каждой дуге пути поток величины 2. (Любая большая величина будет выше пропускной способности некоторых дуг.) Дугам, не входящим в рассматриваемый путь, первоначально припишем потоки, равные нулю. Полученный в результате поток показан на рис. 7.8, b.

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

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

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

Рис. 7.9.

Если допустимый поток в сети то соответствующий граф приращений есть ориентированный граф, имеющий те же самые вершины, что и сеть Дуги этого грифа определяются следующим образом: для каждой дуги из в графе строится дуга а, если а дуга а с обращенной ориентацией если Если в графе есть дуга а или а, то можно добавить или соответственно вычесть единицу потока в а, не нарушая допустимости потока по этой дуге. На рис. 7.9 (справа) показан граф приращений, соответствующий сети. Допустимый поток изображен на рис. 7.9 слева.

(Тройка чисел у дуг обозначает ветственно.)

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

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

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

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

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

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

Так как

для каждого разбиения данное значение должно реализовать и величина потока равна

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

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

При для каждой дуги допустимый поток обязательно существует и теорема 7.5 в этом случае называется теоремой о максимальном потоке и минимальном разрезе [4],