Дискретно-непрерывная математика (стр. 91 )

β(а) называются верхней и нижней границами пропускной способности дуги а и интерпретируются как максимально и минимально до­пустимая величина потока по каждой дуге. Если α(а)=0 для всех а А, то β(а) обычно называется пропускной способностью дуги а, а сеть называется транспортной сетью. Поток φ в сети называется допустимым тогда и только тогда, когда

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

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

v в w?

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

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

В дальнейшем мы будем предполагать, что рассмат­риваемая сеть

N=(V, А) с ограниченной пропускной способностью имеет п вершин, которые мы обозначим через v1, v2, .... vn, и что мы интересуемся только до­пустимыми потоками из v1 в vn (при этом мы должны включить в рассмотрение и потоки, имеющие нулевую величину).

В качестве первого шага на пути получения ответа па поставленные вопросы отметим, что границы про­пускных способностей дуг, входящих в каждый разрез, разделяющий v1 и vп, определяют верхнюю и нижнюю границы величин допустимых потоков. Если X и Y— два множества вершин (не обязательно непересекающиеся), Х→Y обозначает множество дуг типа а(х, у), где хХ, уY. Обозначим через X' дополнение к X относительно V. Напоминая терминологию, относящуюся к разрезам, укажем, что если X и X' оба непусты, то Х→Х' и Х'→Х являются двумя ориентированными разрезами, соответ­ствующими разбиению вершин {X, X'}.

Теорема 6.3. Если φ — любой допустимый поток из v1 в vп, a W — любое множество вершин такое, что v1W и vп W′ , то величина k потока φ должна удовлетворять следующим неравенствам:

Доказательство. Так как Q(v1)=k и Q(v)=0 для всех остальных vW , то мы имеем

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

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

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

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

и

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

Рассмотрим сеть, изображенную па рис. 6.7.

Рис. 6.7.

Пара целых чисел у некоторых дуг представляет ограничения на пропускную способность α(а) и β(а) соответственно. Выбирая

W= {v1, v2, v3, v4}, видим, что

С другой стороны, взяв W= {v1}, имеем

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

Упражнение 6. Для сети рис. 6.7 найти все возможные разби­ения вершин на множества W и W′ так, чтобы v1W и v3 W′. Оцените суммы в условиях теоремы 3 и найдите и . (Положите α = β = 3 на двух вертикальных дугах.)

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

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

Теорема 6.4. Пусть φ — допустимый поток из v1 в vn, имеющий величину k. Если существует допустимый по­ток φ*, имеющий величину k *≠ k, то существует т = | k *—k| простых потоков по цепям {σ1, σ2,.....,σт} из v1 в vn таких, что является допустимым потоком, имеющим величину k* (знак плюс ставится в слу­чае k*>k, а минус в случае k*<k).

Доказательство. Предположим, что k*>k. Тог­да φ *— φ есть поток из v1 в vn, имеющий величину т. Используя теорему 2, можем записать

где σi и — согласованные простые потоки по цепям и циклам соответственно (число потоков по циклам не определено, и они вообще могут отсутствовать). Тог­да, используя теорему 1, находим, чтоогра­ничен потоками φ и Так как поток ограничен двумя допустимыми потоками, то он также является допустимым и имеет величину k+m = k*. Случай k*>k доказан. Если k*<k, то доказатель­ство совершенно аналогично и читатель может провести его самостоятельно.

Упражнение 7. Используя обозначения теоремы 4, нарисуйте сеть и два потока φ и φ * (между одними и теми же парами вершин), имеющих величины k=2 и k* = 5. Определите поток φ *— φ и запи­шите его в виде суммы согласованных простых потоков.

Замечание. Теперь можно строго доказать, что множество значений (если оно существует) допустимых потоков является множе­ством последовательных целых чисел. То есть, если су­ществуют допустимые потоки, имеющие величины k и k*>k соответственно, и r—целое число такое, что k<r<k*, то существует допустимый поток, имеющий величину r. Чтобы проверить это, рассмотрим поток φ+ ∑σi, где суммирование включает все r—k простых потоков по цепям, использованных в доказательстве теоремы 4. Этот поток имеет величину r и является допустимым по ранее изложенным причинам.