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

9.3 является обобщением леммы 9.2). Так как разрез (X, X) —

^ c (Qi P ) Jr c (Q^ R ) Jr c (Qi &)•

Поскольку c(S, P ) ^ 0, t o

Таким образом, (P [J Q U S, R) —искомый минимальный раз­ рез (Z, Z), разделяющий узлы TV; и Nj и не пересекающийся с разрезом (X, X). в

Рассмотрим теперь произвольную сеть N, состоящую из п уз­ лов. Будем искать величины максимальных потоков между задан­ ными р узлами сети N. Эти р узлов, между которыми ищется максимальный поток, будем называть полюсами, а остальные п — р узлов будем называть обычными или промежуточными. Пред­ положим, что имеется некоторая другая сеть N ', которая состоит из р узлов, причем величины максимальных потоков между р полюсами сети N равны величинам максимальных потоков меж­ ду р узлами сети N '. (Две сети, имеющие равные величины макси­ мальных потоков между некоторым множеством узлов, назы­ ваются потоко-эквивалентными или просто эквивалентными отно­ сительно этого множества узлов.) Тогда можно найти искомые величины максимальных потоков между р узлами, рассматривая

сеть N ' . Оказывается, что для каждой сети N всегда существует эквивалентная ей сеть N ' , являющаяся деревом. Рассматривае­ мый ниже алгоритм позволяет по сети N построить эквивалентное ей дерево N ’. В этом алгоритме процесс нахождения максималь­ ных потоков между р полюсами сети состоит из двух шагов, кото­ рые повторяются до тех пор, пока не будет построено дерево N ' , эквивалентное исходной сети N.

Рассмотри^ сначала в общих чертах, что представляют собой шаги алгоритма, а затем дадим более ,подробное его описание.

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

Ш а г 2 заключается в нахождении очередной дуги дерева, при этом используется выделенный на шаге 1 минимальный раз­

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

Дадим теперь более подробное описание алгоритма. Сначала произвольным образом выберем два полюса и решим

в исходной сети N задачу о максимальном потоке между ними. При этом будет выделен минимальный разрез (X , X) пропускной способности с (X , X). Он будет символически изображаться двумя «вершинами», соединенными дугой с пропускной способностью Vj = с (X, X) (рис. 9.6.) (Эта дуга является первой дугой дере­ ва N ' .) В одну из вершин поместим все узлы множества X, а в дру­ гую — узлы множества X. Сами вершины будем обозначать сле­ дующим образом: ® , ® , ® и т .д .

Затем выберем в построенном дереве (рис. 9.6) любую вершину, содержащую 2 или более полюсов, выделим в ней два произволь­

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

все узлы из X можно сжать в один узел. Решение задачи о макси­ мальном потоке в сжатой сети дает новый минимальный разрез пропускной способности н2Получается дерево, изображенное на рис. 9.7, где пропускная способность новой дуги равна к2. Заметим, что вершина ® связывается дугой с вершиной ® ,

го разреза величины v2\ вершина @ связывается дугой с (?),.

если множества X и Y принадлежат к одной и той же части раз­ реза величины v2.

Далее процесс разбиения вершин дерева продолжается анало­ гично. На каждом этапе разбиению подвергается некоторая вер­

решается в сети, более простой, чем исходная, благодаря сжатию

min (via, vab, . . vdj), где via, vab, . . ., vdj — пропускные спо­ собности дуг, образующих единственный путь из N t в N }- в постро­ енном дереве Т.

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

сети. По лемме 9.3 существует минимальный разрез (Z, Z), разделяющий узлы N a и N b и не пересекающийся с разрезом

( X , X ) .

Положим для определенности, что N a £Z, N b£Z.. Пусть Z c c l , Z zd X, как .изображено на рис. 9.9. (Случай, когда Z cz X, Z z d X анализируется аналогично.) Существует две возможности:

1) Ni £ Z, 2) Ni £ X П Z. Покажем, что в обоих случаях с (Z, Z) ^

>с ( Х , X).

1)Пусть N i £ Z . Этот узел обозначен на рис. 9.9 символом гь

заключенным в кружок. Тогда разрез (Z, Z) разделяет Ni и N р, c(Z, ~Z)^sfij = c(X, X) (иначе (X, X) не был бы минимальным разрезом, разделяющим N t и Nj).