Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 176
Текст из файла (страница 176)
Но вершина и не подвергается подъему в процессе прохода, а любая другая вершина и, подвергшаяся подъему в процессе данного прохода (в результате вызова Рщснлкое(и)), не имеет после подъема допустимых входящих ребер согласно лемме 26.28. Итак, в конце прохода все ребра, выходящие из и, остаются недопустимыми, и лемма доказана.
° Алгоритм мподнять-в-начало" В алгоритме "поднять-в-начало" поддерживается связанный список Ь, состоящий из всех вершин множества К вЂ” (я, г?. Ключевым свойством данного списка является то, что вершины в нем топологически отсортированы в соответствии с допустимой сетью, как будет показано при рассмотрении инварианта цикла ниже. (Напомним, что согласно лемме 26.26 допустимая сеть является ориентированным ациклическим графом.) В приведенном ниже псевдокоде алгоритма "поднять-в-начало" предполагается, что для каждой вершины и уже создан список соседей и. Л7. Кроме того, предполагается, что и, леха указывает на вершину, следующую за и в списке Ь, и что, как обычно, если и — последняя вершина данного списка, то и.
пехб = ьце. 7лава 24 Задача о максимальнач яотоне 795 ПеьАВеь-ТО-Ркомт(С, з, !) 1 1и!т!АПХе-Ркен.О'19(С, я) 2 ь = С. К вЂ” (з, !), в произвольном порядке 3 зог каждой вершины и е С. К вЂ” (з, !) 4 и. ситтеи! = и. Ь7. Ьеа!( 5 и = Л.Ьеа!( б зтЬПе и Ф ми. 7 оЫ-Ьездн = и.Ь 8 ь7!яснАкое(и) 9 Ь и. Ь ) оИ-ЬегдЫ 1О переместить и в начало списка Е 11 и = и.иез! Алгоритм "поднять-в-начало" работает следующим образом. Строка 1 инициализирует предпоток и высоты теми же значениями, что и обобщенный алгоритм проталкивания предпотока. Строка 2 инициализирует список Л, который содержит все потенциально переполненные вершины в произвольном порядке. Строки 3 и 4 инициализируют указатель ситцев! каждой вершины и таким образом, чтобы он указывал на первую вершину в списке соседей и.
Как показано на рис. 26.10, цикл зтЬПе (строки 6-11) проходит по списку Ь, разгружая вершины. Рассмотрение начинается с первой вершины списка Е (строка 5). На каждой итерации цикла выполняется раз7рузка вершины и (строка 8). Если процедура О!зснАкое изменила высоту вершины и, строка ! 0 перемещает эту вершину в начало списка Е. Чтобы определить, подверглась ли вершина и подъему, перед разгрузкой ее высота сохраняется в переменной оЫ-Ьегдй (строка 7), а затем это значение сравнивается со значением высоты после выполнения процедуры разгрузки (строка 9).
Строка 11 обеспечивает выполнение очередной итерации цикла ттЬПе для вершины, следующей за и в списке Е. Если и была передвинута а начало списка в строке 10, рассматриваемая на следующей итерации вершина представляет собой вершину, следующую за и в ее новой позиции в списке. Чтобы показать, что процедура ПВЕАвеь-То-Ркомт вычисляет максимальный поток, покажем, что она является реализацией обобщенного алгоритма проталкивания предпотока. Во-первых, заметим, что она выполняет операции проталкивания и подъема только тогда, когда онн применимы, что гарантируется леммой 26.29.
Остается показать, что, когда процедура Пн.явн.-ТО-Ркомт завершается, не применима ни одна основная операция. Дальнейшее доказательство корректности построено на следующем инварианте цикла: При каждом выполнении проверки в строке 6 процедуры Пн.Авн.-ТОГкомт список Е является топологическим упорядочением вершин допустимой сети С7 ь = (17, Е5 ь), и ни одна вершина, стоящая в списке перед и, не имеет избыточного потока. Инициализация. Непосредственно после запуска процедуры 1м!т!АшгеРкееьозт з.Ь = Щ и и.Ь = 0 для всех и е 17 — (з).
Поскольку Щ > 2 Глава уб. Задача о максимальном яоглояв 797 Г:.у -т 8() 4 --'-: ~,'Я .7' 5 4 (г) 3 . ~~ . / 2"" — ' " т (йчб (а > х У У г г $2гб --' ', (г / (х г у к И: х з г у к у г Рис. 2б.(В (ироаолямние). (г) Поскольку в списке Ь за вершиной х слсдуаг вершина к, она пояасргастгл разгрузка. Эта вершина пгшннмастся до высоты 1, а всс 8 слиниц избытка потока проталкивакпся в Г.
Поскольку з поднята, она перемещается в начало списка (. (д) Теперь за вершиной к в списке б следует вершина р, так что должна быть выполнсна сс ражрузка. Но поскольку в вершине р избыток отсутствуст, процсдура Ргзснлков туг жс выполняст возврат, и р остается в Ь на своам месте. Затем выполнясгся разгрузка вершины х. Поскольку она также нс имеет кзбытк, процедура Впюнлкся вновь аыполняст немедленный возврат, и х также остается на собстаснном месте в г'. Процедура Ккьдвн.-то-уконт достигает конца списка б и завсршается.
Псрсполнсинык вершин нот, и прсдпоток прсдставллст собой максимальный поток. (так как $' содержит как минимум исток л и сток (), ни одно ребро не яв- ляется допустимым. Следовательно, Еуд = О, и любое упорядочение множе- ства У вЂ” (л, г) является топологическим упорядочением Су г,. Поскольку изначально вершина и является заголовком списка Ь, перед ней нет вершин, следовательно, перед ней нет вершин с избытком потока. Сохранение. Чтобы убедиться в том, что данное топологическое упорядочение сохраняется при проведении итераций цикла тиййе, прежде всего заметим, что к изменению допустимой сети приводят только операции проталкивания и подъема Согласно лемме 26.27 операции проталкивания не приводят к тому, что ребра становятся допустимыми. Поэтому допустимые ребра могут создаваться только подъемами.
Однако после того как вершина и подверглась подъему, согласно лемме 26.28 больше не существует допустимых ребер, входящих в и, но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая и в начало списка Е, алгоритм гарантирует„что все допустимые ребра, выходящие из и, удовлетворяют условию топологического упорядочения. 79В Часть ИЕ Алгорааьыы блл работы с граФаыа Чтобы убедиться в том, что ни одна вершина, предшествующая и в списке Е, не имеет избытка потока, обозначим вершину, которая будет текущей вершиной и на следующей итерации, как и'.
Среди вершин, которые будут предшествовать и' на следующей итерации, находится текущая вершина и (согласно строке 11), и либо больше таких вершин нет (если и подвергалась подъему), либо там находятся те же вершины, что и ранее (если и не поднималась). Поскольку и подверглась разгрузке, она не содержит избытка потока. Следовательно, если и подвергалась подьему в процессе разгрузки, то ни одна вершина, предшествующая и', не содержит избытка потока.
Если же и в процессе разгрузки не поднималась, ни одна вершина, стоящая в списке Ь перед ней, не получила избыток потока при этой разгрузке, поскольку список Е остается топологически упорядоченным все время в процессе разгрузки (как уже отмечалось, допустимые ребра создаются только подъемами, а не операциями проталкивания), поэтому каждая операция проталкивания заставляет избыток потока двигаться только к вершинам, расположенным в списке дальше (или же к л или 1).
И вновь ни одна вершина, предшествукпцая и', не имеет избытка потока. Завершение. Когда цикл завершается, и оказывается за последним элементом списка Ь, поэтому инвариант цикла гарантирует, что избыток всех вершин равен О. Следовательно, ни одна основная операция неприменима. Анализ Покажем теперь, что процедура Кееявее-ТО-Гкомт выполняется за время 0(17з) для любой транспортной сети 0 = (17, Е). Поскольку данный алгоритм является реализацией обобщенного алгоритма проталкивания предпотока, воспользуемся следствием 26.21, которое устанавливает границу 0(И) для числа подъемов, применяемых к одной вершине, и 0(Из) для общего числа подъемов.
Кроме того, в упр. 26.4.3 устанавливается граница 0(ИЕ) для суммарного времени, затраченного на выполнение подъемов, а лемма 26.22 устанавливает границу 0((сЕ) для суммарного числа операций насыщающих проталкиваний. Теорема 26.30 Время выполнения процедуры КееАвее-То-Гко1чт для любой транспортной сети 0 = (17, Е) составляет 0(Из). Даказашеаьсшао. Будем считать "фазой" алгоритма "поднять-в-начало" время между двумя последовательными операциями подъема. Поскольку всего выполняется 0(Из) подъемов, в алгоритме насчитывается 0(Из) фаз. Каждая фаза сдержит не более Щ вызовов процедуры Р1зсняпое, что можно показать следующим образом.
Если процедура Р1зсцАВОе не выполняет подъем, то следующий ее вызов происходит ниже по списку Ь, а длина Б меньше Щ. Если же процедура 17!зснАкое выполняет подъем, то следующий ее вызов происходит уже в другой фазе алгоритма. Поскольку каждая фаза содержит не более ~ 17~ обращений к процедуре Р1зсиАное, а всего в алгоритме насчитывается 0(Из) фаз, число вызовов данной процедуры в строке 8 процедуры КееАвее-То-ЕВО1чт составляет 0(Из). 799 Глава 26 Задача а макешиалькам катане Таким образом, цикл згй11е процедуры Кеелвеь-То-гконт выполняет работу (не учитывал работу, выполняемую внутри процедуры Ршснлкое), не превыша- 0(Ъ з) Теперь необходимо проанализировать работу процедуры Р1зснлкое в коде выполнения данного алгоритма.
Каждая итерация згЬНе в процедуре Р1зснлкое заключается в выполнении одного из трех действий. Проанализируем объем работы при выполнении каждого из них. Начнем с подъемов (строки 4 и 5). В упр. 26.4.3 время выполнения всех О(172) подъемов ограничивается пределом 0(1'Е). Теперь предположим, что действие заключается в обновлении указателя и.сиггепг в строке 8.
Это действие выполняется 0(4(е8гее(и)) раз всякий раз, когда вершина и подвергается подъему, что в целом для вершины составляет 0(Ъ' 1(ебгее(и)) раз. Следовательно, для всех вершин общий объем работы по перемещению указателей в списках соседей составляет 0(Ъ'Е) согласно лемме о рукопожатиях (упр. Б.4.1). Третий тип действий, выполняемых процедурой 01зснлкое, — операция проталкивания (строка 7). Мы уже знаем, что суммарное число насыщающих операций проталкивания составляет О(Ъ'Е). Заметим, что если выполняется ненасы- ШаЮЩЕЕ ПРОтаПКИВаНИЕ, ПРОЦЕДУРа Р1ЗСНЛКСьЕ НЕМЕДЛЕННО ВЫПОЛНЯЕТ ВОЗВРат, поскольку такое проталкивание уменьшает избьпок до О. Поэтому при каждом обращении к процедуре Р1зснлкое может выполняться не более одного ненасышаюшего проталкивания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
