Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 31
Текст из файла (страница 31)
9.20 (б). 9.4. синтвз сети 181 Сеть, в которой выполняется условие 1» ~ )г» при всех 1, у, будем называть допустимой. Для того чтобы сеть была допустимой, необходимо и достаточно, чтобы «» ~ )г» для дуг дерева Т. Необходимость легко следует из того, что множество дуг дерева Т является подмножеством множества всех дуг. Чтобы доказать достаточность, рассмотрим некоторую дугу А;, пе принадлежащую дереву Т. Гак как Т является максимальным связывающим деревом, то г;г(ш~п(г», гж, ...,г,р), где г», гзю..., гэр — длины дУг, обРазУюЩих единственный путь нз Л'~ в )Ур в дереве Т.
Тогда в любой сети, в которой выполняются доминирующие требования, поток ~;г будет удовлетворять следующим условиям: ~;р>ш1п(~», ~зю ...,~ар))ш1п(г», г,.ю ...,гэр)~г~р. (2) Таким образом, если в сети выполняются доминирующие требования, то в ней будут выполняться все условия ~» ~ )г». Следовательно, мол<но учитывать только доминирующие требования. Обозначим через Ь» искомую пропускную способность дуги А». Общая пропускная способность всех дуг в неориептированной 1 с-~ сети равна — ~, Ь». Построим нижнюю границу Сь для этой вели- 2;~' чины в допустимой сети. Рассмотрим произвольный узел дГ1 сети.
Пусть и, = шах г», т. е. максимум берется по всем дугам, инцидентным атому узлу Мп В любой допустимой сети величины Ь» должны быть настолько болыними, чтобы поток величины и1 мог выйти из каждого узла У„т. е. должно быть: ~Ь» ) иь Тогда нижняя граница Сь общей пропускной способности будет 1 равна — ~ и;: 2 Сь = 2",~ и ( 2,.~ Ь» 1 Перейдем к описанию процедуры синтеза сети, предложенной Гомори н Ху (89), которая позволяет построить допустимую сеть с общей пропускной способностью, равной нижней границе Сь. Заметим, что величины и; могут быть получены, если пользоваться только доминирующими требованиями, т. е.
и, = шах г», где максимум берется по дугам дерева Т, инцидентным узлу Мн Пусть имеется некоторое фиксированное дерево Т. Зададим на нем длины дуг г» и подсчитаем при этих г» величину нижней границы Сь. Затем зададим на нем новые длины дуг г» 182 гл. ». многополюсные мАксимАльпые потоки и подсчитаем при этих гз новую величипу нижней границы Сг,.
Пусть теперь дугам этого я«е дерева Т приписапы длины г,";=- = г>>+г;; вычислим при этих г,"; величину нижней границы Сь. Тогда, вообще говоря, получим Сь Сь -р С~., поскольку п>ах гы и шахг; могут пе совпадать па каждом из узлов Х>. Но если > гм (или г;) являются равпомерпыми требованиями, т. е. гы=г для всех дуг из Т, то (3) Теперь рассмотрим две сети, одна из которых имеет пропускные способности дуг Ьы и величины максимальных потоков 1ы, а другая — соответственпо Ь(> и 1(>. Построим третью сеть с пропускпыми способностями дуг Ь,"> =Ьы+Ь(>.
Тогда яспо, что величины Я максимальных потоков в третьей сети удовлетворяют условию 1>>)1>+й (4) Рассмотрим теперь заданное дерево доминирующих требований Т. Обозначим через г, > наименьшую из длин гы дуг этого дерева, а величины гм представим в виде г > + (гм — г > ). Тогда исходное дерево можно разлон<ить ка два дерева, одно из которых обладает равномерными требованиями г„>», а другое— требованиями гм — г; . Второе дерево может состоять из двух или нескольких частей, пе свяаапных между собой, так как гм — гм>а = 0 для некоторых Лы.
Или >ко можно считать, что эти части связаны между собой дугами с пулевыми гы. Заметим, что дерево с равномерными требованиями ге»а является связным, в противном случае (3) пе выполпяется. Например, дерево Т ка рис. 9.20 (б) можно разложить па несколько частей, представленных ка рис. 9.2$. Затем таким же образом может быть разложена каждая часть, облада>ощая неравномерными требовапиямк, и процесс разложения может быть продолжеп до тех пор, пока исходное дерево Т не будет представлено в виде «суммы» деревьев с равкомерными требованиями.
Например, разлоя«ение па рис. 9.24 может быть продолжепо, при атом получится разложение, представленное па рис. 9.22. Пусть термин синтезировать дерево означает: «построитьсеть, в.которой величины 1ы максимальпых потоков больше или равпы требовапиям гы, задакпым ла этом дереве». После того как дерево разложено в сумму поддеревьев с равномерными требованиями, каждое из этих равномерных поддеревьев можно синтезировать по отдельности. Предположим, что удалось кансдое равномерпое поддерево синтезировать так, что общая пропускная способность каждой построенной подсети равняется пи>клей границе Сь.
Тогда в результате суммировапия всех построенных подсетей ед. СИНТЕЗ СЕТИ 188 получится сеть, которая в силу (4) будет удовлетворять исходным требованиям, т. е. будет являться допустимой. Кроме того, в силу (3) построенная сеть будет обладать минимальной общей пропускной способностью дуг.
Таким образом, исходная задача сводится к синтезу равномерного поддерева, т. е. такого, у которого все требования г раз- ы раны г. Для того чтобы осуществить такой синтез, достаточно начертить цикл, проходящий через все узлы синтезируемого поддерева бт) Р и с.
9.21. (в любом порядке), а затем положить пропускную способность каждой дуги цикла равной г/2. Когда поддерево состоит только из двух узлов, чертится соединяющая их дуга с пропускной способностью г. Ясно, что построенная сеть будет удовлетворять всем требованиям равномерного поддерева. Больше того„построенная сеть обладает минимальной общей пропускной способностью дуг. Действительно, в такой сети с и узлами общая пропускная способность дуг равна п г!2, что совпадает с величиной нижней ТРаниды Сь = — ~п = — пг. 2; ' 2 Р ассмотрим, например, рис. 9.22.
Каждое равномерное поддерево может быть синтезировано, как показано на рнс. 9.23. В результате суммирования сетей па рис. 9.23 получится сеть, изображенная на рис. 9.24, которая удовлетворяет всем требованиям, заданным па рис. 9.20 (а), и обладает минимальной общей пропускной способностью т). ст ое При синтезе рапномерного дерева узлы могут лежать на о- П троенном цикле в любом порядке.
Например, вместо цикла, изобрангепиого па рис. 9.23 (а), можпо взять цикл яа рис. 9.25 (а), ') Нет ) Н трудно видеть, что если все требования г . целочисленны, то Задача за сти всегда имеет оптимальное решение„в котором пропускные и способности дуг явля9отся пли целыми, или полуцольтмн числами.— П им. лерми 9 .— РИМ. О,> ~6г> [а) Р и с. 9,22. Ф~) Ог> Р и с. 9,23, Са) Р и с. 9 24 Г и с.
9.25. гл. синтвз сити 188 в результате получится сеть, построенная на рис. 9.25 (б). Если подсчитать величины потоков, то выяснится, что на рис. 9.25 (б) ~ы — — гсг для всех Ан ~ Т, а на рис. 9.24 /н ) гы для некоторых Ан, хотя обе сети обладают одинаковой (минимальной) общей пропускной способностью дуг. Будем решать две задачи. В первой из них буден искать максимально возмоя~ные потоки, а во второй в потоки, удовлетворяющие доминирующим требованиям как строгим равенствам~ ~ы = ггг для Аы с Т. При этом в обеих задачах общая пропускная способность дуг долягпа быть минимальной. Сначала заметим, что минимальная общая пропускная способность Сь зависит не от всех гьп а только от ио Поэтому, после того как величины и; найдены, требования можно поднять до г',"; = = шип (и;, иг), и при этом величины и, и Сь не изменятся. Всякое дальнейшее увеличение гД обязательно приводит к увеличению Сь.
С помощью некоторой процедуры, описываемой ниже, мы можем синтезировать дерево Т* с требованиями ф так, чтобы в построенной сети 7У* величины максимальных потоков ф были равны г1Ь Оказывается, что эта сеть является в некотором смысле доминирующей. Точнее об этом говорится в следующей теореме. ТеОРемА 9.3. Пусть заданы требования гн. Тогда существует. допустимая сеть Х*, обладающая общей пропускной способностью в $ Сь = — ~~~ и; и величинами максимальных погпоков (5) 7гг = пнн (ии иг). Пусть ДГ' — некоторая другая сеть, такая, что Я гни (6) причем по крайней мере одно из требований (6) выполняется как строгое неравенство, и пусть С' — ее общая пропускная способность.
Тогда либо С'~СЬ (7) либо )(е<й (8) Доклзлткчьство . Возможность случая (7) очевидна. Остается доказать, что если Я)гы и С'(Сь", то Я(ф. Если Я)гы, то долгино быть: ~ ~(г)и; = шахги длЯ любого г. Так как 3 У 1 Р 9 1 ~\ —,, '~„"Ь з — С ( Сь =. — ~з ии значит, па самом деле, ~ Ь;; = ии Отсе 1 сюда следует, что 718(ш(н (~Ь;;, А,Ь1';) =пнп(ии и;) =Я. ° г тзб ГЛ, 9. МНОГОПОЛЮСНЫЕ МАКСИМАЛЬНЫЕ ПОТОКИ В эакл1очение параграфа рассмотрим задачу синтеза сети, в которой требования ~ы ) г;;, заданные на дереве Т, выполняются строго как равенства: ~п — — гы, где Ам й Т. (При атом сеть должна обладать минимальной общей пропускной способностью.) Причина, по которой величина потока ~м монет превышать требоваяне гсо заключается в следующем: может оказаться, что при синтезе равномерного дерева получится цикл, обладающий минимальными разрезами, отличными От минимальных разрезов синтезируемого равномерного дерева.
Следовательно, при сиптезе равномерного дерева надо строить такой цикл, у которого пропускные способности минимальных разрезов равны соответствующим длинам дуг синтезируемого равномерного дерева. Например, в цикле па рис. 9.23(а) разрез (Хы Хю Лгэ (Х„Х,) имеет пропускную способность 10, в то время как дуга Аы на рис. 9.22 (а) является раэреэом с пропускной способностью 5. В цикле на рис.
9.25 (а) раэреэ (Хы Л'ю Хз ) Хм Хь) имеет уже пропускную способность, равную 5. Если синтезировать равномерное дерево таким образом, чтобы оно являлось деревом разрезов построенного цикла, то при сложении всех построенных циклов их минимальные разрезы тоже как бы «складываготся», образуя минимальный раэреэ в результирующей сети; при этом исходное дерево Т доминирующих требований становится деревом раэреэов в полученной сети. Поэтому максимальпый поток ~~р между узлами Х; и Хр удовлетворяет условию (9) Ш а г 1. Произвольному узлу иэ Т присвоить пометку 1. Ш а г 2. Пусть некоторые узлы вэ дерева Т получили пометки 1, 2,..., Й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
