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

ношение (5) из § 9.2 для величины максимального потока в сети между двумя несоседними полюсами дерева примет вид

вой части (19) является (по построению дерева) пропускной спо­

щийся с (X, X) и с ( Z , Z ) .

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

изображенной на рис. 9.12. Эта сеть получена с помощью сжатия узлов N u N z, N q (рис. 9.10) в один узел. В результате получаем

минимальный разрез (Nu N 2, N e, N 3, N 5 | iV4) величины 14, изо­ браженный на рис. 9.13. Заметим, что вершина {3, 5} соединена с вершиной {1 , 2 , 6 }, потому что они лежат по одну сторону в ми­

нимальном разрезе, разделяющем N 3 и iV4.

Затем находим максимальный поток между N 3 и N 5 в сети, изображенной на рис. 9.12. В результате получаем минимальный разрез (Nl, N z, N e, N 5, TV4 | N 3) величины 15, изображенный сим­

волически на рис. 9.14.

12 т. ху

Теперь каждая вершина в полученном дереве содержит только по одному полюсу. Таким образом, найдены следующие величины максимальных потоков в сети (рис. 9.14) : / l 3 — /14 — / i5 — 13, / 34= /4 5 = 14, /35 = 15. Они равны соответствующим величинам

максимальных потоков в исходной сети (рис. 9.10).

Если бы потребовалось найти величины максимальных потоков между всеми парами узлов, тогда надо было бы просто продол­ жить описанный процесс: выбрать, например, узлы N i и 7V6, и найти максимальный поток между ними в сети, изображенной

на рис. 9.15. В результате получили бы минимальный разрез (Ni, N z | N e, N 3 , N it N s) величины 17, изображенный на рис. 9.16. После этого надо выбрать узлы N± и N 3 и найти максимальный поток между ними в сети, представленной на рис. 9.17. В резуль­ тате получим минимальный разрез (N1 | iV2, N e, N 3, N t, N &) вели­ чины 18, изображенный на рис. 9.18. С помощью дерева, изобра­ женного на рис. 9.18, можно легко найти величины максималь­ ных потоков между всеми парами узлов (они выписаны в табл. 9.1).

Сети, представленные на рис. 9.18 и 9.10, имеют одинаковые величины fij максимальных потоков между всеми парами узлов. Такие сети, как уже говорилось раньше, называются потоко-экви­ валентными друг другу. Если в 2-х сетях равны величины макси-

Р и с . 9.19,

9.4. Синтез сети (Гомори и Ху [89])

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

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

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

доминирующими требованиями, а построенное дерево — деревом доминирующих требований Т. Например, если заданы числа гг;-, представленные на рис. 9.20(a), то дерево доминирующих требо­ ваний Т изображено на рис. 9.20 (б).

будем называть допустимой. Для того чтобы сеть была допусти­ мой, необходимо и достаточно, чтобы f tj ^ ri7для дуг дерева Т. Необходимость легко следует из того, что множество дуг дерева Т является подмножеством множества всех дуг. Чтобы доказать

путь из Ni в N p в дереве Т. Тогда в любой сети, в которой выпол­ няются доминирующие требования, поток f ip будет удовлетворять следующим условиям:

/ip ^ m in (fa, fjh, • f0p)> m in (гij, rjh, .. . ,r0 p) ^ r ip. (2 )

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

Обозначим через Ъц искомую пропускную способность дуги A tj. Общая пропускная способность всех дуг в неориентированной

сети равна 4- 2 Ьц. Построим нижнюю границу CL для этой вели-

чины в допустимой сети. Рассмотрим произвольный узел N t сети. Пусть ut = max rtj, т. е. максимум берется по всем дугам, инци-

Тогда нижняя граница Сь общей пропускной способности будет равна

Перейдем к описанию процедуры синтеза сети, предложенной Гомори и Ху [89], которая позволяет построить допустимую сеть с общей пропускной способностью, равной нижней границе Cl - Заметим, что величины иг могут быть получены, если пользовать­ ся только доминирующими требованиями, т. е. и( = max г^, где

и подсчитаем при этих г'ц новую величину нижней границы С£. Пусть теперь дугам этого же дерева Т приписаны длины гу =

— гц-\-г'г}\ вычислим при этих г у величину нижней границы С£.

Тогда, вообще говоря, получим C'i^LCL-\-C’L, поскольку maxгу

Рассмотрим теперь заданное дерево доминирующих требова­ ний Т. Обозначим через rmin наименьшую из длин гу дуг этого дерева, а величины гу представим в виде rmin + (гу — rmin).

Тогда исходное дерево можно разложить на два дерева, одно из которых обладает равномерными требованиями rmin, а другое — требованиями Гу — rmin. Второе дерево может состоять из двух

эти части связаны между собой дугами с нулевыми Гу. Заметим,

что дерево с равномерными требованиями гт ;п является связным, в противном случае (3) не выполняется.

Например, дерево Т на рис. 9.20 (б) можно разложить на несколько частей, представленных на рис. 9.21. Затем таким же образом может быть разложена каждая часть, обладающая нерав­ номерными требованиями, и процесс разложения может быть продолжен до тех пор, пока исходное дерево Т не будет представ­ лено в виде «суммы» деревьев с равномерными требованиями. Например, разложение на рис. 9.21 может быть продолжено, при этом получится разложение, представленное на рис. 9.22.

Пусть термин синтезировать дерево означает: «построить сеть, в которой величины /у максимальных потоков больше или равны требованиям Гу, заданным на этом дереве». После того как дерево

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