Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 39
Текст из файла (страница 39)
9.3 Расстановка пометок на сети и поиск по орграфу Чтобы реализовать обсуждавшиеся в предыдущем параграфе улучшения алгоритма пометок без существенного увеличения сложности каждого э~апа, посмотрим сначала на процесс расстановки пометок с несколько иной точки зрения Предполооким, что мы хотим применить подпрограмму расста.
новки пометок в сети ?е'=(э, й )г, А, Ь) с нулевым начальным пото. ком. В этом случае нам не нужно исследовать пропускные способносян и поток; априори ясно, чяо все дуги в А являются прямымп и что нет обратных дуг. Следоваяельно, паша задача расстановки пометок на сети для нахождения увеличивающего пути в очень сильной степени совпадает с применением алгоритма НАЙТИПУТЪ, представленного на рис. 9.6, к орграфу ($', А) с 5= (э) и Т=-(г). После того как увеличивающий путь найден, мы увеличиваем поток вдоль него и продолжаем процесс. А что будет на последующих этапах? Можно ли пх также рассматривать как поиск по орграфу? Дополнительнымп влечениями, которые присутствуют, когда поток не нулевой, являются обратные дуги, исчезновение (т. е, насыщение) определенных прямых дуг и некоторые изменения пропускных способностей.
Оказывается, что расстановка пометок в сети У относительно потока) эквивалентна применению алгоритма НАЙТИПУТЬ к сети Ж()), определяемой следующим образом ') В Вспояпипе сеяь уяеличеяия иг гл. 7. 208 Гл. 9. Задача а максимальном ломаке Определение 9.!. Пусть даны сеть У=(з, г, )г. А, 6) и допустимый поток Г' в ЛГ. Определим сеть У ()) =-(э, г, )', А ((), ас), где А (1) состоит из следующих дуг.
а) Если (и, и)ЕА и )(и, и)(Ь(и, с), то (и, и)ЕА ()) и ис(и, и)= =Ь(и, и) — )(и, и). б) Если (и, с)ЕА и ((и, о))0, то (и, и)ЕА(() н ас(п, и)=)(и, и). Будем называть ас(и, и) дополнигпельной пропускной способносгпью дуги (и, и)ЕА()). П Если А содержит как дугу (с, и), так и дугу (и, и), то в Л'()) могут быть кратные копии этих дуг. Этого можно избежать многими 'способамп. Например, можно заменить любую такую дугу (и, и) в А двумя дугами (и, й) и (ш, и) с той же пропускной способностью, где ес — новая вершина.
В дальнейшем мы будем предполагать, что в Л'(г) нет кратных дуг. Покажем теперь, что Л'()) обладает одним шпересным свойством. Возьмем любой з-г-разрез ()Р', )Р) в сети У(Г). Величина этого разреза, естественно, равна сумме дополнительных пропускных способностей всех дуг сети Л'(г), идущих из )г' в 1Г. Однако такая дуга (и, и) может быть либо прямой дугой (случай а) определения сети Ле())), либо обратной дугой (случай б)).
В первом случае ас(и, и) ==Ь(и, с) — ) (и, с); во втором случае ас(и, и) =) (и, и). Таким образом, величина разреза ()г', В') в Л'()) равна величине разреза ()г', ))г) в Л' минус прямой поток через разрез и плюс обратный поток через разрез, Заметим, что два последних члена дают в точности †)Д, где через (1) мы обозначаем ~ )(К и), т, е, величину потока Г". о,м]ел Отсюда если разрез в М имеет величину С, то этот же разрез в М(г) имеет величину С вЂ” Я. Поэтому если величина лсинимильного разреза в Л' равна Я, то величина минимального разреза в Л'()) равна ф — ф.
Однако по теореме о максимальном потоке и минимальном разрезе в обеих сетях величина минимального разреза равна величине максимального погока. Таким образом, доказано Предложение 1. Если ٠— величина максимального потока в ЛГ, то величина максимального потока в У()) равна Я вЂ” Я. Пример 9.7. Рассмотрим сеть Лг, представленную на рис. 9АО(а), с указанным на цей потоком ).
Сеть Лг()), соответствующая данным Л' и Г, предс|авлена на рис. 9.10(б); зам же показаны дополнительные пропускные способности дуг сети Л'(г). Если бы мы применили подпрограмму расстановки 1юнеток к сети ЛГ относительно потока), мы должны были бы продвигать пометки по прямым и обратным дугам начиная из к Поскольку Л'()) содержит в точности все соответствующие прямые и обрлгные дуги, подпрограмма расстановки пометок относительно ) сводится просто к примененшо алгоритма ПОИСК к Л'()) начиная с ве)шшны к Такая точка зрения исключительно полезна при реализации 9.8. Росстоноеко пометок но сетп и лоиск ло орграфу 209 /=3 /=4 иг 0 5 ~ /=1 /= 2 3 ие / 0 ио (а1 иг[ Д иб П] "е ДЗ (б) (в) Рис.
9,10. Ё;Ръ, . Щ е м — — 5 5 210 Гл. 9. Задача о макеомальком потоке нашей идеи увеличения потока вдоль кратчайшего возможного пути, Это связано с тем, что кратчайшие увеличивающие пути в Х относительно 1' соответсзвуют кратчайшим путям (т. е. путям с наименьшим числом дуг) из з в 1 в сети Л'(1) Мы знаем, как применять ПОИСК для нахождения кратчайших путей: для этого просто используется принцип поиска в ширину — т. е. вершины, которые нужно просмотречь, обрабачываютсн, как в обычной очереди Поиск в ширину разбивает вершины сети А1(1) на непересекающиеся слои (слой О, слой 1,...) в соответствии с их расстоянием (т е числом дуг в кратчайшем пути) от з.
Например, на рис. 9.10(б) указан номер слоя каждой вершины сети Ае(1). Вершина 1 попалаее в слой 4. Учитывая, Что нас интересуют только крогпчойилее пути из з в 1 в сети Ж0), можно произвесзп некоторые дальнейшие упрощения. Прежле всего заметим, чзо кразчайшиьй путь из к в (не может проходить через вершину слоя с большим номером, чем номер слоя, содержащего б В нац.ем примере кратчайший путь из э в о, в сети А1(1) имеет длину 5, и, следователъпю, никакой кратчайший пу~ь из з в 1 не можез проходить через о,; поэтому можно отбросить вершину о, и все луги, иицидентные ей, без позоря какой-либо полезной информации лля этого этапа Аналогично, можно озброснть все вершины, отличные от й лежащие в том лсе слое, что и 1 (такие, как ое и о„в нашем примере), поскольку они также не могут лежать ни на каком кратчайшем пути из ь в 1 Имшотся и лр)гие части сети Ае(1), которые не нужно рассьеатривазь Любой кратчайший путь из з в ( будет начиначься из ве)ряпшы слоя 0 (т е.
з), затем пройле1 через некоторую вершину слоя 1, затем через некоторую вершину слоя 2 н т. д Другими словами, кратчайший путь может содержать только зе дуги, которые идуз из слоя 1 в слой 1+1 лля некозорого 1. Поэтому без потери инзересующей нас информации можно отбросить любую дугу, которая идет из некоторого слоя в слой с мень.
шим номером (подобно луге (о„о„) на рис, 9.10(б)), и любую дугу, которая соединяет лве вергцины одного и того же слоя (подобно дуге (о„о,)). Полученная подсеть АА'(1) сети А'(1), называемая аспомо. гительной сетью относительно 1", привеЛена на рис. 9.10(в). Вспомогательная сеть АА1(1) имеет специальную структуру, наилучшим образом описываемую следующим определением. Определение 9.2. Слоистая сеть (. = (з, 1, (/, А, Ь) — это сеть, в которой множество вершин (У равно объединению непересекающихся множеств (l„, ..., (I„, таких, что ое,=(з), (/~= ((), и Аы () ((у,,х(1,) П /=! Таким образом, вспомогательная сеть АА1(1) является слоистой сетью.
Заметим, что сеть ААе(1) легко построя~в. Для этого при выполнении поиска в ширину на сети Л1(() достаточно хранитьтолько те дуги, которые ведут и новые вершины, и только тс вершины, которые лежат в слоях с»омерамн, меньшими, чем номер слоя, содержа- Э.4, Алгоритм натождгнин максимального потока щего (. Следовательно, построение вспомогательной сети можно осуществить за время 0(1А (1)()=0(1А1). Используя вспомогательную сеть, можно очень легко найти кратчайший увеличивающий путь относительно текущего потока. Более того, отсюда уже всего один шаг до реализации нашей второй идеи улучшения алгоритма пометок, а именно выполнения ~1 "г на одном и том же этапе как можно болыпего числа уве- х=1 1 4 личений потока.
Определение 9.3. Пусть 1 01 Ж=(з, й У, А, Ь) — слоистая сеть. Увеличивающий путь в 3 1о,1 М относительно некоторого потока д называется прямым, если ои пе использует обратоь ол иых дуг. Поток((в сети Х называется туликовым (не максимальныи), если не существует прямого увеличивающего пути в Д1 отно.. ль о д. (-) Танич образом, все чаксимальиые потоки являюзсятупиковыми; однако туишсовый поток а может не быть максимальным, что проиллюстрировано иа рис. 9.11. Нахождение тупикового потока во вспомогательной сети относительно текущего потока соответст' вует нахождению как можно большего числа кратчайших увеличивающих путей иа данном этапе. Эго соображение является основой нашего алгоритма нахождения.максимального потока, описывае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
