Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 160
Текст из файла (страница 160)
Там же предлагается разработать структуру данных, которая позволит выбрать применимую операцию за время О(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 (и, е) — расстояние (количество ребер) от и до е в остаточной сети Су.
Покажите, что в процессе работы процедуры ОВНВШС Риэп КВ1ЛВеь выполняются следующие свойства: если Ь[и] < ]У], то Ь[и] < < б г (и, т), а если Ь [и] > ]У[, то Ь [и] — [У] < ду(и, з). * 26.4-8. Как и в предыдущем упражнении, пусть бу (и, с) — расстояние от и до с в остаточной сети Су. Покажите, как можно модифицировать обобщенный алгоритм проталкивания предпотока, чтобы в процессе работы процедуры выполнялись следующие свойства — если Ь [и] < ]У], то Ь [и] = 61 (и, т), а если Ь [и] > [У], то Ь [и] — ]У] = 61 (и, а).
Суммарное время, затраченное на обеспечение выполнения данного свойства, должно составлять 0 (У Е). 26.4-9. Покажите, что количество ненасышающих проталкиваний, выполняемых процедурой ОВннис Рын КВ1.лвн. в транспортной сети С = (К Е), не превышает 4]У[~ ]Е], если [У[ > 4. * 26.5 Алгоритм "поднять-в-начало" Метод проталкивания предпотока позволяет нам применять основные операции в произвольном порядке.
Однако после пцательного выбора порядка их выполнения и при эффективном управлении структурой сетевых данных, можно Глава 26. Задача о максимальном потоке решить задачу поиска максимального потока быстрее, чем за предельное время 0 (Ъ'зЕ), определенное следствием 26.26.
Далее мы рассмотрим алгоритм "поднять-в-начало" (ге1аЬе!-го-ггоп[), основанный на методе проталкивания пред- потока, время выполнения которого составляет 0 (Ъ'з), что асимптотически не хуже, чем 0 (Ъ'зЕ), а для плотных сетей — лучше. Алгоритм "поднять-в-начало" поддерживает список вершин сети. Алгоритм сканирует список с самого начала, выбирает некоторую переполненную вершину и, а затем "разгружает" ее, т.е. выполняет операции проталкивания и подъема до тех пор, пока избыток в и не станет равен О. Если выполнялось поднятие вершины, то она переносится в начало списка (отсюда и название алгоритма: "поднять-в- начало"), и алгоритм начинает очередное сканирование списка. Для исследования корректности и временных характеристик данного алгоритма используется понятие "допустимых'* ребер: это ребра остаточной сети, через которые можно протолкнуть поток.
Доказав некоторые свойства сети, состоящей из допустимых ребер, мы рассмотрим операцию разгрузки а затем представим и проанализируем сам алгоритм "поднять-в-начало". Допустимые ребра и сети Пусть С = (К Е) — некоторая транспортная сеть с источником в и стоюм 1, у' — предпоток в С, а Ь вЂ” функция высоты.
Ребро (и, и) называется допустимым РебРам (адш1зз1Ые едйе), если сг(и,и) > О и Ь(и) = Ь(и) + 1. В пРотивном случае ребро (и, и) называется недопустимым (1пайп(зз1Ые). Допустимой сетью (абш1зз(Ые пепчогк) является сеть Су ь = (К Еу ь), где Еу, — множество допустимых ребер. Допустимая сеть состоит из тех ребер, через которые можно протолкнуть поток.
Следующая лемма показывает, что такая сеть является ориентированным ациклическим графом. Лемма 26.27 (Допустимая сеть является ациклической). Если С = Я Е)— неюторая транспортная сеть с источником в и стоюм 1, 1' — предпоток в С, а Ь— функция высоты, тогда допустимая сеть Су ь = (К Еу ь) является ациклической. Доказательство. Доказательство проводится методом от противного. Предположим, что Сук содержит некоторый циклический путь р = (ио,иы..., иь)„где ио = иь и Ь > О. Поскольку каждое ребро пути р является допустимым„справедливо равенство Ь (и; г) = Ь (и;) + 1 для г = 1, 2,..., Ь. Просуммировав эти равенства вдоль циклического пугн, получаем: Ь(ич 1) = ~~ (Ь(и;)+1) = ~~) Ь(сч)+/с. 1=1 Часть Ч1 Алгоритмы для работы с графами 776 Поскольку каждая вершина циклического пути р встречается при суммировании по одному разу, приходим к выводу, что к = О, что противоречит первоначальному предположению.
Следующая лемма показывает, как операции проталкивания и подъема изменяют допустимую сеть. Лемма 26.28. Пусть С = (У, Е) — транспортная сеть с источником а и стоком г, г" — предпоток в С, и предположим, что атрибуг Ь вЂ” функция высоты. Если вершина и переполнена и ребро (и,п) является допустимым, то применяется операция Рцзн(и, о). Данная операция не создает новые допустимые ребра, однако она может привести к тому, что ребро (и, о) станет недопустимым.
Доказательсюиво. По определению допустимого ребра, из и в е можно протолкнуть поток. Поскольку вершина и переполнена, применяется операция РОзн(и, е). В результате проталкивания потока из и в и может быть создано только одно новое остаточное ребро (п, и). Поскольку 1з [ю] = 6 [и] — 1, ребро (и, и) не может стать допустимым. Если примененная операция является насыщающим проталкиванием, то после ее выполнения су (и, э) = О и ребро (и, э) становится недопустимым. и Лемма 26.29. Пусть С = (Ъ; Е) — транспортная сеть с источником а и стоком г, г" — предпоток в С, и предположим, что атрибут й — функция высоты. Если вершина и переполнена и не имеется допустимых ребер, выходящих из и, то применяется операция Кщ.хввг.(и).
После подъема появляется по крайней мере одно допустимое ребро, выходящее из и, но нет допустимых ребер, входящих в и. Доказательство. Если вершина и переполнена, то, согласно лемме 26.15, к ней применяется или операция проталкивания, или операция подъема. Если не существует допустимых ребер, выходящих из и, то протолкнуть поток из и невозможно, следовательно, применяется операция Кщ.лвц.(и). После данного подъема 6 [и] = 1+ шш (1з [о]: (и, е) е Е~).
Таким образом, если ц — вершина, в которой реализуется минимум указанного множества, ребро (и, о) становится допустимым. Следовательно, после подъема существует по крайней мере одно допустимое ребро, выходящее из и. Чтобы показать, что после подъема не существует входящих в и допустимых ребер, предположим, что существует некоторая вершина е, такая что ребро (и, о) допустимо.
Тогда после подъема 6 [е] = Ь [и] + 1, так что непосредственно перед подъемом л [е] > л [и] + 1. Но, согласно лемме 26.13, не существует остаточных ребер между вершинами, высоты которых отличаются более чем на 1. Кроме того, подъем вершины не меняет остаточную сеть. Таким образом, ребро (о, и) не принадлежит остаточной сети, следовательно, оно не может находиться в допустимой сети. Глава 2б. Задача о максимальном потоке Списки соседей Ребра в алгоритме "поднять-в-начало*' обьединены в так называемые "списки соседей". В заданной транспортной сети С = (У, Е) списком соседей (пе1яЬЬог Ы) Ю [и] некоторой вершины и Е У является односвязный список вершин, смежных с и в С.
Таким образом, вершина и оказывается в списке Ф [и] только в том случае, если (и, и) е Е или (и, и) е Е. Список соседей И [и] содержит только такие вершины и, для которых может существовать остаточное ребро (и, и). На первую вершину в списке Ж [и] указывает указатель беад [АГ [и]]. Для вершины, следующей за и в списке соседей, поддерживается указатель пех1-пездббог [и]; этот указатель имеет значение я~, если и — последняя вершина в списке соседей. Алгоритм "поднять-в-начало" циклически обрабатывает каждый список соседей в произвольном порядке, который фиксируется в процессе выполнения алгоритма.
Для каждой вершины и поле ситтеп1 [и] указывает на текущую вершину списка Ю [и]. Первоначально сиггепг [и] устанавливается равным беаН [М [и]]. Разгрузка переполненной вершины Переполненная вершина и разгружаешся (йзсйагяес1) путем проталкивания всего ее избыточного потока через допустимые ребра в смежные вершины, при этом, если необходимо, производится подъем вершины и, чтобы ребра, выходящие из вершины и, стали допустимыми. Псевдокод разгрузки выглядит следующим образом: Ензснлксв(и) 1 зт)з11е е[и] > О 2 йо и — ситтеп1[и] 3 Ни = ып. 4 тпеп Кв~лвв~(и) 5 сиггеп1[и] — леал [7Ч [и]] 6 е!яен с7(и,и) > О и 6[и] = 7з[и]+1 7 Феп Рын(и, и) 8 е1ке ситтеп1[и] — пехг-пегдббог[и] На рис.
26.9 показаны несколько итераций цикла иййе (строки 1-8), тело цикла выполняется до тех пор„пока вершина и имеет положительный избыток. Каящая итерация выполняет одно из трех действий в зависимости от текущей вершины и из списка соседей Аг [и]. На рисунке показаны только смежные с у вершины и ребра, входящие в у или выходящие из нее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
