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

получится сеть, которая в силу (4) будет удовлетворять исходным

пропускной способностью дуг.

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

Р и с . 9.21.

(в любом порядке), а затем положить пропускную способность каждой дуги цикла равной г/2. Когда поддерево состоит только из двух узлов, чертится соединяющая их дуга с пропускной способностью г. Ясно, что построенная сеть будет удовлетворять всем требованиям равномерного поддерева. Больше того, построен­ ная сеть обладает минимальной общей пропускной способностью дуг. Действительно, в такой сети с п узлами общая пропускная способность дуг равна п-г/2 , что совпадает с величиной нижней

Рассмотрим, например, рис. 9.22. Каждое равномерное подде­ рево может быть синтезировано, как показано на рис. 9.23. В ре­ зультате суммирования сетей на рис. 9.23 получится сеть, изобра­ женная на рис. 9.24, которая удовлетворяет всем требованиям, заданным на рис. 9.20 (а), и обладает минимальной общей пропуск­ ной способностью *).

При синтезе равномерного дерева узлы могут лежать на по­ строенном цикле в любом порядке. Например, вместо цикла, изображенного на рис. 9.23 (а), можно взять цикл на рис. 9.25 (а),

!) Нетрудно видеть, что если все требования rtj целочисленны, то задача синтеза сети всегда имеет оптимальное решение, в котором пропускные способности дуг являются или целыми, или полуцелыми числами,— Прим,

перев.

Р и с. 9.22.

должна обладать минимальной общей пропускной способностью.) Причина, по которой величина потока может превышать тре­ бование Гц, заключается в следующем: может оказаться, что при синтезе равномерного дерева получится цикл, обладающий мини­ мальными разрезами, отличными от минимальных разрезов синте­ зируемого равномерного дерева. Следовательно, при синтезе рав­ номерного дерева надо строить такой цикл, у которого пропускные способности минимальных разрезов равны соответствующим дли­ нам дуг синтезируемого равномерного дерева. Например, в цикле

разрезом с пропускной способностью 5. В цикле на рис. 9.25 (а) разрез (Ni, N 2, N 3 | N t, N 5) имеет уже пропускную способность, равную 5.

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

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

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

Рассмотрим процедуру расстановки пометок, которая по дан­ ному дереву Т строит нужный цикл.

Ш а г 1. Произвольному узлу из Т присвоить пометку 1.

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

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

узел, смежный узлу к — 1. Если да, то пометить его А; + 1; если нет, то перейти к узлу к — 2 и проверить, найдется ли непомечен­ ный узел, смежный узлу к — 2 , и т. д.

Ш а г 3. После того как все узлы дерева Т окажутся помечен­ ными, построить следующий цикл: 1, 2, . . ., п, 1. Этот цикл является искомым.

На рис. 9.26 приведены два возможных варианта расстановки пометок в дереве с помощью описанной процедуры.

Докажем, что для цикла, полученного в результате расстанов­ ки пометок, дерево Т является деревом разрезов. Для этого рассмотрим произвольную дугу 11} дерева. Например, возьмем

Если дугу li} удалить из дерева, то оно распадется на две компо­ ненты связности В и С, одна из которых будет содержать узел N t, а другая — N j х). Пусть к — наибольшая из пометок узлов, попавших в ту же компоненту, что и Nj. Тогда узел с пометкой

J) Нам нужно доказать, что в синтезирующем цикле компоненты В жС соединены ровно двумя дугами. Для этого достаточно показать, что если помечен какой-то узел из С, то перейти обратно в В можно лишь после того, как будут помечены все узлы из С. Предположим, что узел 1 лежит в В. Из алгоритма видно, что в С мы могли попасть только по дуге 1 ^ . Значит,

узел i уже был помечен. Следовательно, нет ни одной дуги дерева, которая вела бы из С в непомеченный узел из В. Так как все узлы в С по алгоритму получают индексы большие, чем уже помеченные узлы в В, то попасть в В мы можем только «обратным ходом», просматривая все помеченные в С узлы.— Прим, перее.