Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 29
Текст из файла (страница 29)
Чтобы использовать зту идою более полно, изучим некоторые свойства минимальных разрезов в сети. Будем говорить, что деа разреза (Х, Х) и (У, У) пересекаются, если каждое из четырех множеств узлов Х Ц У, Х () У, Х Д У, Х Д У непусто. Леммл 9.1. Пусть (Х, Х) — минимальный разрез, разделяющпй узел )У~ сХ и некоторый узел из Х, и пусть гв'н )в"ьЕХ. Тогда найдется минимальный разрез (Я, 2), разделяющий Д'~ и Уь, который не пересекается с разрезом (Х, Х). Доквзвтельство.
?(усть (У, У) — минимальный разрез, разделяющий )у, и )в'ь, и допустим, что он пересекается с разрезом (Х, Х). Определим следующие множества: Х()У=(), ХП У=Я, Х()~ =-Р, ХПУ=Л (как показано на рис. 9.3). 9.3. Анллиз сети 169 Есть две возможности: )У;ЕД или 1г';РЯ. 1. Пусть Х~ЕД, )УрЕР, )т"ьЕЛ. Так как (Х, Х) является мнпималы<ым разрезом, разделяющим )у; и некоторый другой узел из Х, то, сравнив его У с разрезом (~1, РОЛ() Я), получин Р с((), Р)+с(Я, Р)+с(О, Л)+ — , 'с (Я, Л)(с 0;1, Р) + -Р М, Л)+с((), Я) (1) Так как Х Х с(Я, Р))0, (2) то из (1) слсдуот, что с(Я, Н)(с((1, Я).
(3) Поскольку 0(с(Р, Я), Р к с. 9.3 то, сложив (3) и (4) и прибавив к обеим частям (с (Р, Л) + с (~), Л)), получим с (Р, Л) )- с Ог, Л) + с (Я, Л) ( с (Р, Л) + с ((), Л) + с (ф, Я) + +с (Р, Я). (5) Левая часть неравенства (5) представляет собой пропускную способность разреза (Р()чоЯ, Л), который разделяет узлы гУ, и )Уь и не пересекается с (Х, Х). Правая часть неравенства (5) есть величина пропускной способности минимального разроза (у', л'), разделяющего Л~ н )г'ю Таким образом, (РОЧ() Я, Л) является искомым минимальным разрезом (г', У).
11. В случае когда узел Д"; Р Я, можно аналогично показать, что (Р, Ч () Л () Я) является искомым минимальным разрезом, разделяющим У~ п )Уь и пе пересекающимся с (Х, Х). Итак, осли (Х, Х) — минимальный разрез, то при подсчете величины максимального потока между двумя узлами из Х можно сжать в один узел все узлы мпожоства Х.и Ламма 9.2.
Пусть (Х, Х) — произвольный минимальный разрез, отделяющий заданный узел )У~ Е Х от какого-либо другого узла сети. Пусть У, — произвольлыи узел из Х. Тогда найдется минимальный разрез (2, 2), разделяющий узлы )У; и Хь который не пересекается с разрезом (Х, Х). гл. ». многополюснык млксимлльнык потони Доклзлтклы:тво. Пусть (У, У) — минимальный разрез, разде- ляющий узлы Х; и Уь который пересекается с (Х, Х). Пусть, как и в предыдущей лемме, Х()У=~1, Х() У=-Я, Х()У=Р, Х()У=Н, где )У~ Е П, а У; Е () (рис. 9.4). Так как (Х, Х) является минимальным разрезом, то, как и при доказательстве леммы 9.1, можно получить неравенство (5).
В левой ого части стоит величина пропускной способности У разреза (Р () ч () Я, г»), разде- лЯ«ощего )У; и Д'ь В пРавой части (5) стоит величина пропускной способности ми~~и- мального разреза (У, У). Таким образом, (Р () 0 () Я, Л) является искомым разрезом (г, г). ° Из леммы следует, что если (Х, Х) является минимальным разрезом, отделяющим )У; с Х от некоторого р другого узла сети, и требуется найти величину мавр и с. 9.4.
симальиого потока г;ь где Х, — произвольный узел из то множество Х может быть «сжато» в один узел. Х, Лкимл 9.3. Пусть (Х, Х) — минимальный разрез, разделяющий заданные узлы Л'«и Уь, )У; — произвольный узел из Х, Язв произвольный узел из Х. Тогда существует минимальный разрез (Я,2), разделяющий узлы У~ и )У;, который не пересекается с разрезом (Х, Х). Доклзлткльство. Предположим, что (У, Г) — минимальный разрез, разделяющий Х; и Ж~ и пересекающийся с разрезом (Х, Х).
Тогда Д, = с (У, У). 11усть (рис. 9.5) Х() У =Я, Х П 'У = П. Х() У.-=~, ХП 1'=Р З.з. АБАлиз скти Не теряя общности, можно считать, что Л~; Е(1, ]У7ЕЛ. В зависимости от того, где лежат )уь и ]уь, возможны трн случая (остальные случаи симметричны). 1. Пусть Л'.Е(3, ]У 60 У 1Уь Е Л, Л'1Е Л. Тогда из (1) — (5) следует, что (Р (] 0 Ц Я, Л) является искомым минимальным разрезом. э П. ПУсть )У,СЯ, Л;С1',), Хьс Р, 1У7ЕЛ. Так как разрез (Х, Х) — минимальный из разрезов, разделяющих ]у, и ]т'ь, а (Я, 1'0(~(]Л) — раз- рез.
раздсляквций Л'„и Мь, то сф, Р) +с((7, Л) — , 'с(Я, Р) — ' + с(Я, Л)(с(Я, ())лл — , 'с(Я, Р)+с(Я, Л). У В силу с ((), Л) > 0 имеем с ((7, Р) ( с (Я, б)) = с ((), Я) . (6) Поскольку разрез (Р, ~) (] Я (] Л) такнье разделяет Л', и Л~ь, то с(Х, Х) =сф, Р) Рс((), Л)+с(Я, Р)+с(Я, Л)< <с(К Р)+с(Я, Р)-~-с(Л, Р). В силу с(ч, Л) > 0 имеем с(Я, 17)<с(Л, Р)=с(Р, Л). (7) Так как с(Р, Я)>0, то с(Р, Л)-;-2сф, Л)+с© Я) <с(Р, Л)+ +2с((1, Л)+с(б), Я)+2с(Р, Я). Складывая (6), (7) н (8), получаем ]с(17, Р)+сф, Л) — , 'с(1с Я)] —;(с(Р, Л)+сф, Л) ~ с(Я, Л)]" <2[я(Р, Л) — 'с(1', Я)-] с(ф, Л)+с((), Я)] (9) (8) или с Ж, Р (] Л (] Я)+с(Р (] (7 (] Я Л) <2с(У У) (10) Отсюда следует, что по крайней море одна из величин сф, Р и (] Л (] Я), с(Р (] ч (] Я, Л) не больше, чем с(У, У).
Поскольку каждый из трех разрезов, фигурирующих в (10), отделяет )т"; и М,, а (У, У) — минимальный из них, то либо ГЛ. 9. МНОГОПОЛЮСНЫЕ МАКСИМА:ГЬНЫЕ ПОТОКИ 472 (1Е, Р () Л () Я), либо (Р () 9 () Я, Л) является искомым минимальным разрезом (7, 2), разделяюнгим узлы ЕУ, и Уе и не пересекающимся с разрезом (Х, Х). П1. Пусть дг, бф, Ог;б(Е, ЕуьбР, Е)гебЛ (в атом случае леагиа 9.3 является обобщением леммы 9.2).
Так как разрез (Х, Х)— минимальный из разрезов, разделяющих УА и Етю а ((Е, Р () О Л О Я) — некоторый разрез, разделяющий Еу, и Лы то с(Х, Х) =;.с(бЕ, Е () Л () б) или, в более подробной записи, с((Е, Р)+с(Я, Р)-~ с((Е, Л)+с(Я, Л)< (сф, Р)+сф, Л)+сф„Я). Поскольку с (Я, Р ) ) О, то с(Я, Л)<с(К Я), а так как с(Р, Я)- О, та с(Р, Л)-'" с(ф, Л) < с(Л. Л) †'.с(ф, Л) †' с(Р, Я). Склады вая (11) и (12), пол у чаем (11) (12) с(Р, Л)+сОЕ, Л) —;с(Я, Л)( <с(Р, Л) 1-сф, Л) с(Р, Я)+сф, Я) (13) или с(Р () () () Я, Л) < с(У, Г).
(14) Таким образом, (Р () бЕ () Я, ЕЕ) — искомый минимальный разрез (7, 7), разделяющий узлы Ог~ и Уе и не перосекающийся с разрезом (Х, Х). и расемотрим теперь пронзвольнуго сеть дг, состоящую из и узлов. Будем искать величины максимальных потоков между заданными р узлами сети Е1'. Зги р узлов, меягду которыми ищется максимальный поток, будем нааывать полюсами, а остальные и — р узлов будем называть обычными или промежуточными. Предпологким, что имеется некоторая другая сеть ЕУ', которая состоит из р уалов, причем величины максимальных потоков между р полюсами сети Е1' равны величинам максимальных потоков между р узлами сети дг .
(две сети, имеющие равные величкпы максимальных потоков между некоторым множеством узлов, называются потово-аквпвалентными или просто зквпвалентными относительно зтого множества узлов.) Тогда можно найти искомые величины максимальных потоков между р узлами, рассматривая ».3. анализ сктн 17З сеть Х'. Оказывается, что для каждой соти А' всегда существует эквивалентная ей сеть Л"', являющаяся деревом. Рассматриваемый ниже алгоритм позволяет по сети У построить эквивалентное ей дерево У'.
В этом алгоритме процесс нахождения максимальных потоков между р полюсами сети состоит из двух шагов, которые повторяются до тех пор, пока не будет построено дерево Л", эквивалентное исходной сети А . Рассмотрим сначала в общих чертах, что представляют собой шаги алгоритма, а затем дадим более подробное его описание. Ш а г 1 заключается в решении задачи о максимальном потоке между двумя выбранными полюсами, причем обычно эта задача решается в сети, меныяей, чем исходная сеть )у, так как некоторое мно;кество узлов сжато в один узел. Прн нахождении максимального потока выделяют минимальный разрез, затем переходят к шагу 2.
1Б а г 2 зак.ночается в нахождении очередной дуги дерева, нрн этом используется выделенный на шаге 1 минимальный разрез, (Алгоритм заканчивается, когда найдено р — 1 дуг дерева.) Далее выбирается некоторая новая пара полюсов и осуществляется сжатие некоторых подмножеств узлов исходной сети, в результате чего получается сеть, которая будет использоваться в следующий раз на шаге 1. После этого переходят к шагу 1. Дадим теперь более подробное описание алгоритма. Сначала произвольным образом выберем два полюса и решим в исходной сети )у задачу о максимальном потоке между ними.
Прн этом будет выделен минимальный разрез (Х, Х) пропускной способности с (Х, Х). Он будет символически изобра"каться двумя чвершина»»из, соединенными дугой с пропускной способностью из —— - с (Х, Х) (рнс. 9.6.) (Эта дуга является первой дугой дерева Ж .) В одну из першин поместим все узлы множества Х, а в другую — узлы множества Х. Сами вершины будем обозначать следующим образом: ®, ®, 0г и т. д. Затем выбере»~ в построенном дереве (рис. 9,6) любую вершину, содержащую 2 нлн более полюсов, выделим в ней два произвольных полюса, сожмем узлы другой вершины в одни узел и решим задачу о максимальном потоке между двумя выделеппымн полюсами в сжатой сети.
)1апример, выделим два полюса в (г). Тогда все узлы из Х можно сжать в один узел. Решение задачи о максимальном потово в сжатой сети дает новый минимальный разрез пропускной способности в». Получается дерево, изображенное на рис. 9.7, где пропускная способность новой дуги равна гм Заметим, что вероника ф связываетсн дугой с вершиной ф, 174 Гл. г. Многополюсные мАксимАльные потоки если множества Х и У принадлежат к одной и той же части нового разреза величины ог, вершина ® связывается дугой с ®, Р в с.
9.6. Р н с. 9.7. если множества Х и У принадлежат к одной и той 'ке части разреза величины ог. Далее процесс разбиения вершин дерева продолжается аналогично. Па каждом этапе разбиению подвергается некоторая вершина ®, которая содернсит не меньше двух полюсов. Если вершину ® удалить из дерева, то оно распадается на несколько компонент связности (рис. 9.8). При решении задачи о максимальном потоке между двумя полюсами нз От все узлы, кроме узлов нз Ог, попавшие в одну компоненту связности, сжимаются в один узел.
После того как задача о максимальном потоке будот решена р — 1 раз, будет построено дерево Т, каждая вершина которого содержит ровно один полюс и, может бьггь, пер и с. 9.8. ОЕРшнна У содернвт не- сколько промежуточных узскольно нолгоссв. лов. (Заметим, что задача о максимальном потоке обычно решается в сети, более простой, чем исходная, благодаря сжатию некоторых узлов.) Совсем но очевидно, что построенное дерево Т эквивалентно исходной сети У. Факт этот вытекает из следующей теоремы, Теогем т 9.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
