Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

166 ГЛ. 9. МНОГОПОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОКИ

из этих трех чисел не равно двум другим, то оно долйшо быть боль­

ше, иначе снова получим противоречие с (1). Если начертить ”^ге ^

а третья сторона будет больше или равна другим. Таким образом, неравенство (1 ) является своего рода «неравенством треугольни­

(в сети с п узлами) существует не более п — 1 различных. Докажем

это следующим образом. Рассмотрим полный граф с п^п ^ дуга­

ми, длины которых пропорциональны соответствующим величи­ нам максимальных потоков. Выберем среди этих дуг те, которые образуют максимальное связывающее дерево. Оказывается, что каждая из величин f i} должна быть равна длине одной из п — 1

дуг этого дерева. Предположим, что f ln — одна из величин f tj, которая не равна ни одной из длин дуг дерева. Существует един­ ственный путь из N { в N n, состоящий из дуг рассматриваемого максимального связывающего дерева. Из (5) следует, что величи­ на fin должна быть больше или равна минимальной из длин / ;;- дуг, входящих в этот путь. Если бы величина / 1п была строго больше, то мы могли бы заменить минимальную из дуг, входящих в путь, дугой длины / 1п. При этом получилось бы другое связы­ вающее .дерево с общим весом, большим, чем у максимального связывающего дерева, что невозможно.

Достаточность. Построим сеть, в которой заданный набор чисел ntj, удовлетворяющих условию (1 ), будет множеством вели­

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

Для этого числа ntj, j > i, удовлетворяющие условию (1), будем считать длинами дуг некоторого полного графа. Найдем в этом графе максимальное связывающее дерево. Затем рассмотрим сеть, имеющую ту же структуру, что и построенное дерево, у которой пропускные способности дуг btj равны заданным числам п^. Покажем, что в этой сети поток между N t и N j, такой, что / i7- = = пи, будет максимальным. Действительно, для любой пары уз­ лов этой сети выполняется соотношение

/ij = min ipu, bi2l . . . , bqj) = min (пц, nl2, . . . , nqJ),

чено выше, для чисел пц, удовлетворяющих условию (1 ) (а следо-

вательно, и условию (5)), справедливо

пц = min (пи, п12, . . nqj).

Таким образом, f i} = п ц .ш

Заметим, что при доказательстве достаточности мы показали, что если некоторое множество чисел является множеством вели­ чин максимальных потоков (или, как говорят, реализуемо в ка­ честве множества максимальных потоков), то оно реализуемо деревом.

9.3. Анализ сети (Гомори и Ху [89])

Обратимся теперь к задаче анализа потоковой сети. Имеется неориентированная сеть с ограниченными пропускными способ­ ностями дуг bij. Требуется найти величины максимальных потоков

дой парой узлов, а достаточно решить лишь р — 1 задач о макси­

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

Рассмотрим сначала процесс, называемый сжатием нескольких узлов в один узел. Основная идея состоит в том, что несколько узлов сети принимаются за один (рис. 9.1). Другими словами, можно считать, что дуги между всеми «сжимаемыми» узлами полу­ чают бесконечную пропускную способность. При этом дуги, свя­ зывающие некоторый узел N t (не принадлежащий к числу сжи­ маемых) со всеми сжимаемыми узлами, заменяются одной дугой с пропускной способностью, равной сумме пропускных способ­ ностей заменяемых связывающих дуг.

Например, если сжать узлы N 3, N e и N 8 в один узел (рис.. 9.1), то получится сеть, изображенная на рис. 9.2. В сети на рис. 9.1

дуг, не принадлежащих этому минимальному разрезу (У, У),

не повлияет на величину с (У, У) и может лишь увеличить про­ пускную способность других разрезов, разделяющих N 2 и Х 7. Таким образом, при сжатии узлов N 3, N e, N 8 разрез (У, У)

останется минимальным разрезом, разделяющим N 2 и N 7. Следо­ вательно, при вычислении максимального потока / 27 можно,

например, сжать узлы N 3, N 6, N a в один и производить вычисле­ ния в сети, изображенной на рис. 9.2.

Чтобы использовать эту идею более полно, изучим некоторые свойства минимальных разрезов в сети. Будем говорить, что два

разреза (X, X) и (У, У) пересекаются, если каждое из четырех множеств узлов X П Z f) У, X [\ Y , X [\ Y непусто.

Лемма 9.1. Пусть (X, X) —минимальный разрез, разделяющий узел N i £ X и некоторый узел из X , и пусть N t, N k ^X . Тогданайдется минимальный разрез (Z, Z), разделяюгций Ni и Nu, который не пересекается с разрезом (X, X).

пересекается с разрезом (X, X).

Д оказательство. Пусть (У, У) — минимальный разрез, разде­ ляющий узлы N t и N ь который пересекается с (X , X). Пусть, как и в предыдущей лемме,

Лемма 9.3. Пусть (X , X) — ^минимальный разрез, разделяю­ щий заданные узлы N а и N ь, N г — произвольный узел из X, N j —

произвольный узел из X. Тогда существует минимальный разрез (Z, Z), разделяющий узлы N ; и N j, который не пересекается с раз­ резом (X, X).