Алгоритмы - построение и анализ (1021735), страница 159
Текст из файла (страница 159)
Тогда в процессе выполнения процедуры Ончещс Рцзн Кн.Авн. в С число подъемов не превышает 2[Ц вЂ” 1 для одной вершины, а их общее количество не более (2 [Ц вЂ” 1) ([Ц вЂ” 2) < 2 [1'[~. Доказательсогво. Во множестве У вЂ” (з,1) только [Ц вЂ” 2 вершин могут быть подняты. Пусть и Е У вЂ” (з, $). Операция КЕЬАВЕЬ(и) увеличивает высоту Ь [и]. Значение Ь [и] первоначально равно 0 и, согласно лемме 26.21, возрастает не более чем до 2 [Ц вЂ” 1. Таким образом, каждая вершина и Е Ъ'- (з, г) подвергается подьему не более 2 [Ц вЂ” 1 раз, а общее число выполненных подъемов не превышает (2[1'[ — 1) ([1'[ — 2) < 2[Ц . Лемма 26.21 помогает также определить границу юличества насыщающих проталкиваний. Лемма 26.23 (Граница количества насыщающих проталкиваний).
В процессе выполнения алгоритма Оекек~с Рпзн КеьАееь для любой транспортной сети С = (Р; Е) число насыщающих проталкиваний меньше, чем 2[У[[Е[. Доказашезьсигво. Для любой пары вершин и,и Е Ъ' рассмотрим насыщающие проталкивания от и к и и от и к и (в обе стороны), и назовем их насыщающими проталкиваниями между и и и.
Если есть хотя бы одно такое проталкивание, то хотя бы одно из ребер (и, и) и (и, и) является ребром Е. Теперь предположим, что произошло насыщающее проталкивание из и в и. В этот момент Ь [и] = Ь [и]— — 1. Чтобы позднее могло произойти еше одно проталкивание из и в и, алгоритм сначала должен протолкнуть поток из и в и, что невозможно до тех пор, пока не Часть Ч!.
Алгоритмы для работы с графами 772 будет выполнено условие Ь [и) = Ь [и) + 1. Поскольку Ь [и) никогда не уменьшается, для того чтобы выполнялось условие Ь [и) = Ь [и] + 1, значение Ь [и) должно увеличиться по меньшей мере на 2. Аналогично, Ь [и] должно увеличиться между последовательными насыщающими проталкиваниями из и в и как минимум на 2. Высота изначально принимает значение О и, согласно лемме 26.21, никогда не превышает 2 ($'( — 1, откуда следует, что количество раз, когда высота вершины может увеличиться на 2, меньше (Ц.
Поскольку между двумя насыщающимя проталкиваниями между и и и хотя бы одна из высот Ь [и) и Ь [и] должна увеличиться на 2, всего имеется меньше 2(Ц насыщающих проталкиваний между и и и. Умножив это число на число ребер, получим, что общее число насыщающих проталкиваний меньше, чем 2 Щ (Е(. й Следующая лемма устанавливает границу числа ненасышающих проталкиваний в обобщенном алгоритме проталкивания предпотока. Лемма 26.24 !Граница количества ненасыщающих проталкиваний). В процессе выполнения алгоритма Овчнк!с Рази Кпьлвнь для любой транспортной сети С = [Ъ; Е) число ненасыщающих проталкиваний меньше 4 (Ц~ [(Ц + (Е().
Доказатявльсигво. Определим потенциальную функцию Ф = ~"„.,О,1>о Ь [и]. Изначально Ф = О и значение Ф может изменяться после каждого подъема, насыщающего и ненасыщающего проталкивания. Мы найдем предел величины, на которую насыщающие проталкивания и подъемы могут увеличивать Ф. Затем покажем, что каждое ненасыщающее проталкивание должно уменьшать Ф как минимум на 1, и используем эти оценки для определения верхней границы числа ненасышающих проталкиваний. Рассмотрим два пути увеличения Ф. Во-первых, подъем вершины и увеличивает Ф менее чем на 2 Щ, поскольку множество, для которого вычисляется сумма, остается прежним, а подъем не может увеличить высоту вершины и больше, чем ее максимально возможная высота, которая составляет не более 2 (Ц вЂ” 1 согласно лемме 26.21.
Во-вторых, насыщающее проталкивание из вершины и в вершину и увеличивает Ф менее чем на 2 (Ц„поскольку никаких изменений высот при этом не происходит, и только вершина и„высота которой не более 2 (Ц вЂ” 1, может стать переполненной. Теперь покажем, что ненасыщающее проталкивание из и в и уменьшает Ф не менее чем на 1.
Почему? Перед ненасыщающим проталкиванием вершина и была переполненной, а и могла быть переполненной или непереполненной. Согласно лемме 26.14, после этого проталкивания и больше не является переполненной. Кроме того, после данного проталкивания и должна быть переполненной, если только она не является источником. Следовательно, потенциальная функция Ф уменьшилась ровно на Ь (и]„а увеличилась на О или на Ь (и]. Поскольку Ь [и)— — Ь [и] = 1, в итоге потенциальная функция уменьшается как минимум на !. Глава 26.
Задача о максимальном потоке Итак, в ходе выполнения алгоритма увеличение Ф происходит благодаря подъемам и насыщающим проталкиваниям; согласно следствию 26.22 и лемме 26.23, это увеличение ограничено, и составляет менее (21У~) (2 Щ ) + +(2(Ц) (2~Ц (Е!) = 4 Щ~((У1+ )Е!). Поскольку Ф > О, суммарная величина уменьшения и, следовательно, общее число ненасыщаюших проталкиваний меньше, чем 4 Щ~ ()Ц + (Е(). И Определив границу числа подъемов, насыщающего проталкивания и ненасыщающего проталкивания, мы заложили основу дальнейшего анализа процедуры бнчиыс Ризн КиьАввь, а также любых других алгоритмов, основанных на методе проталкивания предпотока.
Теорема 26.25. При выполнении процедуры Оечеис Ризи КеьАвнь для любой транспортной сети С = (У, Е) число основных операций составляет О (УвЕ). Доказалгельслюво. Непосредственно вытекает из уже доказанных следствия 26.22 и лемм 26.23 и 26.24. Таким образом, алгоритм завершается после О (УзЕ) операций. Итак, осталось предложить эффективные методы реализации каждой операции и выбора подходящей выполняемой операции. Следствие 26.26.
Существует реализация обобщенного алгоритма проталкивания предпотока, которая для любой сети С = (У, Е) выполняется за время О (У2Е) Доказательство. В упражнении 26.4-1 предлагается показать, как реализовать обобщенный алгоритм, в котором на каждый подъем затрачивается время О (У), а на каждое проталкивание — О (1). Там же предлагается разработать структуру данных, которая позволит выбрать применимую операцию за время О(1).
Тем самым следствие будет доказано. И Упражнения 26.4-1. Покажите, как реализовать обобщенный алгоритм проталкивания пред- потока, в котором на каждый подъем затрачивается время О (У), на каждое проталкивание — О (1), и то же время О (1) — на выбор применимой операции; суммарное время выполнения при этом составляет О (УзЕ). 26.4-2. Докажите, что время, затрачиваемое в целом на выполнение всех О (Уз) подъемов в обобщенном алгоритме проталкивания предпотока, составляет только О (У Е).
Часть Ч1 Алгоритмы для работы с графами 774 26.4-3. Предположим, что с помощью алгоритма проталкивания предпотока найден максимальный поток для транспортной сети С = (У, Е). Разработайте быстрый алгоритм поиска минимального разреза в С. 26.4-4. Разработайте эффективный алгоритм проталкивания предпотока для поиска максимального паросочетания в двудольном графе. Проанализируйте время его работы.
26.4-5. Предположим, что все пропускные способности ребер транспортной сети С = (К Е) принадлежат множеству (1, 2,..., Ь). Проанализируйте время выполнения обобщенного алгоритма проталкивания предпотока, выразив его через ]У], ]Е] и /с. (Указание: сколько ненасыщающих проталкиваний можно применить к каждому ребру, прежде чем оно станет насыщенным?) 26.4-6. Покажите, что строку 7 процедуры 1ьпт~лшхн Ркнг~.отт можно заменить строкой 7 Ь[а] - [У[С]] — 2 и это не повлияет на корректность или асимптотическую производительность универсального алгоритма проталкивания предпотока.
26.4-7. Пусть 61 (и, е) — расстояние (количество ребер) от и до е в остаточной сети Су. Покажите, что в процессе работы процедуры ОВНВШС Риэп Ка.ЛВеь выполняются следующие свойства: если Ь[и] < ]У], то Ь[и] < < б г (и, т), а если Ь [и] > ]У[, то Ь [и] — [У] < ду(и, з). * 26.4-8. Как и в предыдущем упражнении, пусть бу (и, с) — расстояние от и до с в остаточной сети Су.
Покажите, как можно модифицировать обобщенный алгоритм проталкивания предпотока, чтобы в процессе работы процедуры выполнялись следующие свойства — если Ь [и] < ]У], то Ь [и] = 61 (и, Г), а если Ь [и] > [У], то Ь [и] — ]У] = 61 (и, а). Суммарное время, затраченное на обеспечение выполнения данного свойства, должно составлять 0 (У Е). 26.4-9. Покажите, что количество ненасышающих проталкиваний, выполняемых процедурой ОВннис Рын КВ1.лвн. в транспортной сети С = (К Е), не превышает 4]У[~ ]Е], если [У[ > 4. * 26.5 Алгоритм "поднять-в-начало" Метод проталкивания предпотока позволяет нам применять основные операции в произвольном порядке.
Однако после пцательного выбора порядка их выполнения и при эффективном управлении структурой сетевых данных, можно Глава 26. Задача о максимальном потоке решить задачу поиска максимального потока быстрее, чем за предельное время 0 (Ъ'зЕ), определенное следствием 26.26. Далее мы рассмотрим алгоритм "поднять-в-начало" (ге1аЬе!-го-ггоп[), основанный на методе проталкивания пред- потока, время выполнения которого составляет 0 (Ъ'з), что асимптотически не хуже, чем 0 (Ъ'зЕ), а для плотных сетей — лучше. Алгоритм "поднять-в-начало" поддерживает список вершин сети.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
