Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 168
Текст из файла (страница 168)
Причина этой разницы в определениях станет ясной позже в этом разделе. На рис.26.5 показан разрез ((л,емег),(ез,ее,г)) транспортной сети, представленной на рис. 26.1, (б). Чистый поток через данный разрез равен Дем ез) +1(ег,еа) — )(ез, вг) = 12+ 11 — 4 = 19, а пропускная способность данного разреза составляет с(ез, ез) + с(ег, еа) = 12 + 14 = 26. Следующая лемма показывает, что для заданного потока У чистый поток через любой разрез одинаков и равен величине потока ф. Пусть )' представляет собой поток в транспортной сети ( ' со стоком а и истоком т и пусть (Я, Т) — произвольный разрез ег.
Тогда чистый поток через разрез (Б, Т) равен Х(о, Т) = )Д. Глава 76. Задача а макеималькам латаке 76! Доказалеельсяево. Условие сохранения потока для любого узла и Е $' — (а,1) можно переписать как ~~> 7(о,е) — У 7(ввн) =О. (26.11) вЕУ С учетом определения (Д из уравнения (26.1), добавляя равную О левую часть уравнения (26.11), и суммируя по всем вершинам в Я вЂ” (я), получим ~л=Кл,)-Кл,)~ К Кл,)-Ел, ° )) вЕУ вЕУ иея — 1е) веУ вЕУ Расширение правой суммы и перегруппировка членов дает ~Д = ~~~ 7(я,с) — ~ 1(с,я) + ~ ~ 7(иве) — ~ ~ ((сви) иея-1л) век иЕя-(л) вЕУ З(а,с)+ ~ З(п,о) — ~~~ З(с,е)+ У З'(сви) вЕУ иеЯ-(е) вЕУ иеЯ-(л) = ~~ь ~ь ('(и,с) — ~ ~~~ 7'(у,и) .
вЕУ иЕЯ вЕУ иЕЯ Поскольку 17 = Я1ЗТ и Яй Т = 9, мы можем разбить каждое суммирование по $' на суммы по 5 и Т и получить Щ = У ~~~ 7'(и, У) + ~ ~~~ 7(и, с) — ~~~ ~ 7(св и) — ~~~ ~ Г(с,и) вЕЯ иЕЯ вЕТ иЕЯ вЕя иЕя ветиея = ~~> ~~~ Г (и, у) — ~~~ ~~ь 7'(с, и) .етиея етиея + ~~„По,н) -'Я'Я1(У,4 вея иея веяиея Две суммы в скобках на самом деле одинаковы, поскольку для всех вершин х, у е Я член 7" (х, у) в каждую сумму входит по одному разу. Следовательно, эти суммы сокращаются, и мы имеем ~Д = ~~~ ~~ )(о,о) — у ~~~ 7'(с,и) иеявет иея ет = 7(Я,Т), Следствие леммы 26.4 показывает, как пропускные способности разрезов можно использовать для определения границы величины потока.
Части П. Алгоритмы даа работы с графами Следствие 26.5 Величина любого потока г" в транспортной сети С ограничена сверху пропускной способностью произвольного разреза С. Доказательство. Пусть (Я,Т) представляет собой произвольный разрез С и пусть ) является произвольным потоком. Согласно лемме 26.4 и ограничению пропускной способности ~)., = ~(я,т) )(и,и) — ~ ~ ~)(и,и) иез ят ибб иЕТ ( ~~~ ~~~ )'(ис и) ийб ивт ( ~~~ ~~~ с(и, и) иябиет = с(Я,Т) . Непосредственно из следствия 26.5 вытекает, что величина максимального потока в сети ограничена сверху пропускной способностью минимального разреза.
Сейчас мы сформулируем и докажем важную теорему о максимальном потоке и минимальном разрезе, в которой утверждается, что значение максимального потока равно пропускной способности минимального разреза. Теорема 26. 6 (О максимальном потоке и минимальном разрезе) Если ) представляет собой поток в транспортной сети С = (Ъ; Е) с истоком в и стоком 1, то следующие утверждения эквивалентны. 1. г" является максимальным потоком в С. 2.
Остаточная сеть С) не содержит увеличивающих путей. 3. ф = с(о', Т) для некоторого разреза (Я, Т) транспортной сети С. Доказательсгпво. (1) =ь (2): предположим противное: пусть ) является максимальным потоком в С, но С) содержит увеличивающий путь р. Тогда, согласно следствию 26.3, поток, полученный путем увеличения потока г" на поток )р, где )р задается уравнением (26.8), представляет собой поток в С с величиной, строго большей, чем 1Д, что противоречит предположению о том, что )' является максимальным потоком.
(2) ~ (3): предположим, что С) не содержит увеличивающего пути, т.е. что в С) нет пути из в в 1. Определим Я = (и е вг: в Су имеется путь из а ни ) и Т = )г' — Я. Разбиение (Я, Т) является разрезом: в Е Я выполняется тривиально, а 1 (с Я, поскольку в С) нет пути из в в 1. Теперь рассмотрим пару вершин и е 5 и и Е Т. Если (и,и) Е Е, должно выполняться )'(и,и) = с(и,и), поскольюг убЗ глава Зб. Задача о максимальном логлоке в противном случае (и,о) Е Ег, что помещало бы вершину о в множество Я. Если (о, и) е Е, должно выполняться Д(о, и) = О, поскольку в противном случае значение су(и, о) = До, и) должно было бы быть положительным и мы должны были бы иметь (и, о) е ЕТ, так что о должно было бы находиться в Я.
Конечно, если ни (и, о), ни (о, и) не находятся в Е, то 7" (и, о) = 7'(о, и) = О. Таким образом, имеем З" (Я, Т) = ~~г ~~г 7" (и, о) — ~~г ~~1 Зг(о, и) оЕЯ ЕТ сЕТ оЕЯ с(и, о) — ~~г ~~г О сеТ оел иЕЯ еЕТ = с(Я,Т) . Следовательно, согласно лемме 26.4 )З") = 7(Я, Т) = с(Я, Т). (3) =р (1): согласно следствию 26.5 ~~~ < с(Я,Т) для всех разрезов (Я, Т). Таким образом, из условия ~Д = с(Я, Т) вытекает, что поток З является максимальным потоком. Базовый алгоритм Форда-Фалкерсвна При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р и используем р для того, чтобы изменять поток З.
Как предлагается леммой 26.2 и следствием 26.3, мы заменяем З на Г" 7 ур, полУчаЯ новый поток, величина котоРого Равна ) 7') + ~~р1 ПРиведеннаЯ далее реализация данного метода вычисляет максимальный поток в транспортной сети С = (17, Е) путем обновления атрибута потока (и, о).З каждого ребра (и, о) Е Е'. Если (и, о) ф Е, неявно предполагается, что (и, о).З = О. Мы также считаем, что вместе с транспортной сетью задаются пропускные способности с(и, о) и что с(и, о) = О, если (и, о) ф Е. Остаточная пропускная способность сг(и, о) вычисляется по формуле (26.2).
Выражение су(р) в коде процедуры является просто временной переменной, в которой хранится остаточная пропускная способность пути р. РОкО-Рш.кекбОы(С, вг ь) 1 1ог каждого ребра (и, о) е С. Е 2 (и,о).7" = О 3 тсййе существует путь р из а в 1 в остаточной сети СЗ 4 су(р) = ш(п(су(и,о); (и, о) содержится в р) 5 1ег каждого ребра (и, о) в р 6 1г (и,о) Е Е 7 (и, о)./ = (и, о).З + су(р) 8 е!ае (о, и).7 = (о, и). 1 — с7(р) Вспомиим из раалела 22п, что мы орсдставллем атрибут 7 длл ребра (о, с) с помешаю того же сапог обозиачеииа — (и, с). 7, — по и в случае атрибутов любого другого обьекта.
7б4 Часть Р?. Алгоритмы вввя работы с графами в 4!12 (вз ( .г, (в] Рис. 2б.б. Работа базового алгоритма Форда-Фаякерсона. (а)-(д) Последовательные итерации цикла тййе. Слева в каждой части показана осттачная сеп Сг из строки 3 с вьщеленным увеличивающим путем р. Спртт показан новый поток 7", ипорый является результатом увеличениа 7 на гр. Остаточная сечь в (а) представляет собой входную сеть С.
Процедура гОйп-р(л.кбкво)ч является расширением приведенного ранее псевдокода Гойи-Р(л.кбкбо)4-Мбтноп. На рис. 26.6 показаны результаты каждой итерации при тестовом выполнении. Строки 1 н 2 инициализируют поток 7" значением О. В цикле зчЬ|е в строках 3-8 выполняется неоднократный поиск увеличивающего пути р в Су и увеличение потока 7" вдоль пути р увеличивается на остаточную пропускную способность су()з). Каждое остаточное ребро в пути р является либо ребром исходной сети, либо обратным к ребру в исходной сети.
В строках 6-8 выполняется обновление потока, соответствующее каждому случаю, путем добавления потока, если остаточное ребро является ребром исходной сети, и вычитания в противном случае. Когда увеличивающих путей больше нет, поток 7" является максимальным. Анализ метода Форда-Фалкерсена Время выполнения процедуры г Окп-Г~~.кбкзО)ч зависит от того, как именно выполняется поиск увеличивающего пути р в строке 3.
При неудачном выборе метода поиска апгорнтм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно будет сходиться к макси- Глава 2б. Эадача о максиюыьлаы лалшле уб5 3 :-ей;:„, .„'Улз 8 4 йт12 Г:„,-, 'Йз .4'' де ма 11Л4 ' ьг -"' 11Л 2 ут ~-,)у О 71 ь .,~;:~';"; -ь(ь ~ "ктв) — — — 1 (,Ивс'з 11/14 т:„: У Рис. 2б.б (предолнииие).
(е) Остаточная сеть при последней проверке цикла иьйе. В ней нет увевнчнвмошия путей, так что поток 5, показанный в части (д), является максимальным. Величина найденного максимального потока равна 23. мальному значению потоказ. Если увеличивающий путь выбирается с использованием поиска в ширину (который мы рассматривали в разделе 22.2), алгоритм выполняется за полиномнальное время.
Прежде чем доказать этот результат, получим простую границу времени выполнения для случая, когда увеличивающий путь выбирается произвольным образом, а все значения пропускных способностей являются целыми числами. На практике задача поиска максимального потока часто возникает в целочисленной постановке. Если пропускные способности являются рациональными числами, можно использовать соответствующее масштабирование, которое сделает их целыми. Если обозначить максимальный поток в таюй трансформированной сети как У', то в случае непосредственной реализации процедуры РОКОР(л.кнйзом цикл ьтийе в строках 3-8 выполняется не более ~~'~ рвз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
