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