Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 23
Текст из файла (страница 23)
Пусть с(ЕЕ, Е') = ~' Ь». Аналогично определим еф, Л), н;ео к г с(Я, Е') и т. д. Так как (Х, Х) — минимальный разрез, разделяющий Л; и )1'з, а Я, Е' () Л () Я) — таня;е разрез, разделяющий Аг, и Ез'и то с(Х, Х) а сф, Р()Л()Я).
Или, что то же самое, еф, Р)+еф, Л)+ -';сф, Р)-:;-с(Я, ЕЕ)(е((Е, Р)+с((Е, Л)+с(ч, Ь), откуда с(Я, Р) — , 'е(Я, Л) =с(0, Я). (3) з( несколько, например х„, .= хзз = тзз -- хзз = хзз остальные хм = О; нли х с = тгг = хгз = — хзт = хзз остальные хц — О. (Х, Х) и (У, У) — минимальные разрезы, Тогда (Х()У, ХНУ) и (ХПУ, ХПУ)— также минимальные разрезы, разделяющие 1У, и Хо и утверьндение теоремы верно. Пусть Х и У пересекаются. Рассмотрим рис.
8.3. Введем обозначения: в.!, ввкдкник 14! Поскольку с(Х, Х)»с(РО !ЕОЯ, Л), т. е. сЯ, Р)+с((7, Л)+с(Я, Р) Рс(Я, Л)» <с(Р, Л)+с© Л)+с(Я, Л), получаем с(~Е, Р) ~ с(Я, Р)»с(Р, Л). Аналогично из выражения с(У, У) сф, Р() Л() Я) с(Р, Л)+с(Р, Я)»с((), Р), а из выражения с(У, У)»с(Р() !ЕЦЯ, Л) следует с(Р, Я)~с(!',), Я)»с(Я, Л). Складывая (3), (4), (5) и (6), получим 2с(Я, Р) ,' Так как Ь!!)О, то (4) находим (5) (6) 2с(Р, Я)»0. с(Я, Р) = с(Р, Я) =О. Подставляя (7) в (3), (4), (5) и (6), имеем с(Я, Л)»с(Ч, Я), с(а Р)»с(Р, Л), с(Р, Л)»с(~), Р), с((), Я)»с(Я, Л), (7) откуда следует с(Я, Л) =с© Я), с((7, Р) =с(Р, Л). Из (7), (8) и (9) имеем с(Х, Х) =с(!,Е, Р)-)-сф, Л)+с(Я, Л)=- =с((7, Р)+с((), Л)+сф, Я) =-с(Х() У, Х() У), с(Х, Х) =с(!,1, Р)-рс(ч, Л)+с(Я, Л) =- =с(Р, Л) — 'с(ч, Л)+с(Я, Л)=-с(Х() У, Х Д У). ° (8) (9) Так как существует много минимальных разрезов, возникает естественный вопрос: какой нз минимальных разрезов получается в конструктивном доказательстве теоремы о максимальном потоке и минимальном разрезе? Пусть (Хь Х;) (! —.1, ..., и) — все минимальные разрезы, разделяющие А!, и А!!.
Пусть (Х, Х)— минимальный разрез, полученный в конструктивном доказательстве теоремы 8.1. Тогда Х = () Х;. з=! г.!. 3. млнсимлльныи ноток «42 Чтобь~ доказать этот факт, покажем сначала, что разрез Л3 ТР! ( () Хг, () Х;) нвляетсн минимальным. Пусть (Х», Х,) и (Хз, Х )— !=! ! — ! любые два минимальных разреза. Тогда из теоремы 8.2 следует, что (Х, () Хз, Х! Д Хз) — тожо миш»мальныи разрез. Пусть (Х», Х») — еще один минимачьный разрез.
Снова используя теорему 8.2, мы получаем, что (Х,() Х«Д Х», Х»() Хз() Х») — тоже минимальпь!и разрез. Гол»! этот процесс повторим и — ! раз, то получим, что (Х,()Х»()... ()Х, Х,()Х«!')... ()Х,„) — мипимальпыи разроз. Теперь заметим, что рекурронтпоо опредоление мно»кества Х не мо»кет быть использовано для того, чтобь! пометить какой- нибудь узел из Х, если величина потока в сети равна с(Х, Х).
Отскща слодует, что множество Х по содержит в качество собствекного подмножества ни одного из множеств Х;. таких, что (Х;, Х;)— минимальный разрез. В частности, Х пе может содержать в качество собственного подмножества н ('! Хь Следовательно, учиты! —. ! вая, что множество Х я!ияется одним из множеств Хо получим Х= ПХо ° !=! 8.2. Метод расстановки пометок для нахождения максимального потока Мы у»ке рассмотрели конструктивное доказательство теоремы о максимальном потоке и»!якима!!ьнол! разрезе. Теперь остановимся подробнее на алгоритме нахождения максимального потока. »(ак уже отмечалось в з 8.», задача о максимальном потока в соти может быть сформулирована как задача липейпого программирования.
Однако метод расстановки пометок но является частным случаем симплекс-метода. В симплекс-методе происходит движение от одной вор!кипы многогранника к другой, пока не будет достигнута оптимальная. Как станет ясно а дальнейн!ем, в методе расстановки пометок дело обстоит но так. Метод расстановки пометок начинается с произвольного потока (в качестве начального можно взять нулевой поток). Затем продпринимаотся попытка получить поток с больпгей величиной. Бычисг!опия заканчиваются, когда получен максимальный поток. Алго1н»тм заключается в систематическом поиске всех возможных путей из А'» в А'!, увеличива»ощих поток.
Зто осуществляотся с помощюо процедуры «расстановки пометок». Узлы получают специальныо «пометки», указывающие направление, в котором |бз «.з. Метод Ресстдновки никиток может быть увеличен некоторый дуговой поток. После того как найден некоторый путь, увелнчнвающнй поток, определяют величину максимальной пропускной способности этого пути; далее поток увелнчиваа>т на зту величину, а все пометки на узлах стирают.
Затем начннаотся расстановка новых пометок узлов исходя нэ только что полученного потока. Алгоритм состоит из двух <нагов. Шаг 1 — это процесс, в ходе которого узлы получают пометки. Шаг 2 заключается в изменении потока. В[зги 1 и 2 повторяются до тех пор, пока увеличвние потока становится невозможньы|. Ш а г 1 (процесс расстановки по,четоя). На шаге 1 каждый узел находится в одном нэ трех состояний: «помечен н просмотрен», «`омечен н не просмотрен» или «пе помечен». Вначале все узлы не помечены. Пометка произвольного уала Л'! всегда состоит нэ двух частой. Первая часть — индекс < узла У<, который указывает, что можно «послать» поток иэ )<>< в >«|.
Вторая часть пометки — число, указывающее максимальную величину потока, который можно «послать» пз источника «<, а Л>|, не нарун<ая ограничений па пронускцые способности дуг. Прежде всего источник <г', получает пометку [в', е (е) = оо). Первая часть этой пометки означает, что можно послать поток иэ узла У» в этот же узел; символ оо означает, что величина потока не ограничена сверху. Теперь узел У, «помечен н не просмотрен», а все остальные узлы «пе помечены».
Вообще выберем лх>бой помеченный н непросмотренный узел ><>. Пусть <>н имеет пометку [<'", е (1)) илн [<, е (1)). Два узла будем называть соседними, если они соединены дугой. Иэ всех узлов, соседних с )<>|, ныцелим те узлы й ю которые пе помечены и для которых х|„~ Ь;».
Припишем ка>кдому узлу У» пометку 11', е (й)), где и (>с) = ппп [е (1), б|» — х>»[. (Такие узлы й е теперь «помечены и не просмотрены».) После этого всем соседним с Х| узлам <><», которые не помечены и для которых х„) О, приписываем пометку [/, е (><)[, где е (><) =. >н[п [е ()), х»>1 '). (Такие узлы )<» теперь также «помечены н пе просмотрены».) Теперь все узлы, соседние с У>э име|от пометки. Тогда узел <<<| счнтаотся помеченным и просмотренным, и его можно бо«ьп<е не рассматривать па этом шаге. Может оказаться, что некоторые соседние с <>'| узлы помечены, а осталын<е не могут быть помечены (либо все соседние с ))<| узлы не могут быть цомечены); в этих случаях узел )><| также <) Для неорнентвроваююа ду>ч< мы могли бы определять е (к) = = <в!в [е (/).
е» т 6>«[. Лто повысило бы пронусвну>о способность нуги, увеличивающего ноток. Есле принять таку>о эрец«дуру, то появление отрицательного дугового нотояа на шаге 2 (измен<нне потока) будет означать, что дуговой ноток имеет в»нрав«евве, вротввоноло>евое вавравяеаюо первоначального дугового потока. Г:!. 8. млнсимллш>ый поток 144 считается помеченным и просмотренным.
Знаки «+» н « — » в первой части пометок указывают, как должен быть изменен поток па шаге 2. Продолжим приписывать пометки узлам, которые являются соседнимн для помеченных и непросмотренных узлов, до тех пор, пока либо узел М> окажется помеченным, либо нельзя будет больше пометить нн одни узел и сток >>>> окажется непомеченным. Если )«'> не может быть помечен, то не существует пути из >>>, в >>>„увеличивающего поток, и, следовательно, цостроепный поток максимален. Если яге Ю, помечен, то на п>аге 2 можно найти путь, увеличивающий поток. Ш а г 2 (изменение потока).
Предпололсим, что сток Ж> имеет пометку (й', е (~)!. Тогда замепнм ль> на хь> + е (г). Если >ке он имеет пометку (Й., е (1)1, то л>ь заменяя на х>ь — з (1). Затем в любом из этих случаев переходим к узлу >>>ь. Вообще если узел >>>ь имеет пометку !у', е (й)1, то л,ь заменим на х;д + е (г) и перейдем к узлу У~', если узел Лгь имеет пометку (1, з (Й)1, то ль> заменим на хь> — е (~) и перейдем к У . Продолжим эти действия, пока не достигнем источника Ул.
После этого сотрем все старые пометки узлов и вновь перейдем к шагу 1. Чтобы обеспечить конечность процесса, будем предполагать, что дуговые пропускные способности Ь» целочисленны. (Ниже будет рассмотрена модификация метода, обеспечивающая конечность процесса при любых неотрицательных Ььь) Когда алгоритм заканчивается па шаге >, то получается множество Х помеченных узлов и множество дуг А>т с >>г> ~ Х, Ф> ц й Х, па которых х» — — Ь>> (и пет дуг Ат>, таких, что х» ) 0).
Отсюда следует, что (Х, Х) — минимальный разрез, поток через который равен его пропускной способности. Таким образом, получен максимальный поток. С другой стороны, каждый раз величина потока увеличивается цо крайней мере на единицу (предполагаем, что пропускные способности дуг и исходный поток являются целочисленными). Поскольку величина максимального потока ограничена сверху пропускной способностью минимального разреза (целым числом), то алгоритм расстановки пометок конечен ').
Рассмотрим сеть, изображенпу>о на рнс. 8.4. Каждой ориентированной дуге поставлено в соответствие 2 числа, Первое из них— >) Если вычисления начались с цолочзслеввого потока, то все последующие цогокя (в частности, максвмальвый), получаемые цри работе рассмотреааого алгоритма, будут цепочке»езиымя. Этот простой, во ваа>лый факт известен под названием теор«мы о цел«числ«он»лгпи> если пропускные способности дуг Зм цолочяолевзь>, то существует максимальный поток, который цолочислов.— При . перев.
з. мвтод глсстлновки помвток 145 зто пропускная способность дуги, а второе — исходный поток по дугам. (Можно использовать в качестве исходного потока любые числа, удовлетворяющие условиям (1), (2). В частности, можно было бы взять .ты = О для всех 1, 1.) 1 111 1П а г 1. Припишем узлу М, пометку [з', оо1. Узел Д', имеет 2 соседних узла. Пометить М~ мы яе мо1кем, так 21 2,2 как Ь„, — х„= 1 — 1 = О, и кет дугового потока х„» О. Узлу 1уз припнпгем пометку [з", 11, поскольку Ь,ив — х,з = 2 — 1 =- 1 и е (2) =- ш[п [е (г), Ь,з — х,з] .= гп[п (оо, 1) =- 1. Теперь узел Х, помечен и просмотрен, а Жз помечен и пе просмотрен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
