Алгоритмы - построение и анализ (1021735), страница 161
Текст из файла (страница 161)
Кроме того, предполагается, что пеИ [и] указывает на вершину, следующую за и в списке Ь, и что, как обычно, если и — последняя вершина данного списка, то пех1 [и] = 1чп.. КеьАВее ТО РЕОыт(С, з,1) 1 1Х!Т1А1!ЕЕ РКЕН.О%(С, а) 2 Ь вЂ” Ъ'[С] — 1а, 1) в произвольном порядке 3 1ог (для) каждой вершины и е Ъ" [С] — [а, г) Глава 26. Задача о максимальном потоке 781 4 !!о сютеп1[и] +- Ьеай [о1 [и]] 5 и — ЬеаН[х ] б згй!!е и ф н!ь 7 Оо оЫ-ЬегдЬ! — Б,[и] 8 П! БСНАКОЕ(и) 9 !!'Ь[и] > оЫ-Ье!дЬ! 1О Феп передвинуть и в начало списка Е 11 и — пех1 [и] Алгоритм "поднять-в-начало" работает следующим образом. Строка 1 инициализирует предпоток и высоты теми же значениями, что и обобщенный алгоритм проталкивания предпотока. Строка 2 инициализирует список Т,, который содержит все потенциально переполненные вершины в произвольном порядке.
Строки 3-4 инициализируют указатель сиггеп! каждой вершины и, чтобы он указывал на первую вершину в списке соседей и. Как показано на рис. 26.10, цикл зчЫ!е (строки 6-11) проходит по списку 1, разгружая вершины. Рассмотрение начинается с первой вершины списка Е (строка 5). На каждой итерации цикла выполняется разгрузка вершины и (строка 8). Если процедура !3!зснАкОв изменила высоту вершины и, строка 10 перемещает эту вершину в начало списка Т,.
Чтобы определить, подверглась ли вершина и подъему, перед разгрузкой ее высота сохраняется в переменной оЫ Ьеф)ц (строка 7), а затем это значение сравнивается со значением высоты после выполнения процедуры разгрузки (строка 9). Строка 11 обеспечивает выполнение очередной итерации цикла зч!з!!е для вершины, следующей за и в списке Е. Если и была передвинута в начало списка, рассматриваемая на следующей итерации вершина— зто вершина, следующая за и в ее новой позиции в списке. Чтобы показать, что процедура Кв1.Авв1. То Рконт вычисляет максимальный поток, покажем, что она является реализацией универсального алгоритма проталкивания предпотока.
Во-первых, заметим, что она выполняет операции проталкивания и подъема только тогда, когда они применимы, что гарантируется леммой 26.30. Остается показать, что когда процедура Кв1.Авв1. То Рконт завершается, не применима ни одна основная операция. Дальнейшее доказательство корректности построено на следующем инварианте цикла: При каждом выполнении проверки в строке 6 процедуры Кв!.Авн. ТО Рконт список Ь является топологическим упорядочением вершин допустимой сети Сдь = (К Еу ь), и ни одна вершина, стоящая в списке перед и, не имеет избыточного потока. Инициализация. Непосредственно после запуска процедуры 1н!т!А1.1ю Рквгсов Ь [а] = [1 "[ и Ь [о] = 0 для всех о Е Ъ' — (з). Поскольку [1"[ > 2 (так как Ъ' содержит как минимум источник а и сток !), ни одно ребро не 782 Часть Ч1.
Алгоритмы для работы с графами является допустимым. Следовательно, Еда = О, и любой порядок множества 1' — (а, т) является топологическим упорядочением Су ь. Поскольку изначально вершина и является заголовюм списка Ь, перед ней нет вершин, следовательно, перед ней нет вершин с избытком потока. Сохранение. Чтобы убедиться, что данное топологическое упорядочение сохраняется при проведении итераций цикла ттЫ1е, прежде всего заметим, что к изменению допустимой сети приводят только операции проталкивания и подъема.
Согласно лемме 26.28, операции проталкивания не приводят к появлению новых допустимых ребер. Поэтому допустимые ребра могут создаваться толью подъемами. После того как вершина и подверглась подьему, согласно лемме 26.29, больше не существует допустимых ребер, входящих в и, но могут быть допустимые ребра, выходящие из нее.
Таким образом, перемещая и в начало списка Ь, алгоритм гарантирует, что все допустимые ребра, выходящие из и, удовлетворяют условию топологичесюго упорядочения. Чтобы убедиться, что ни одна вершина, предшествующая и в списке Ь, не имеет избытка потока, обозначим вершину, которая будет текущей вершиной и на следующей итерации, как и'. Среди вершин, которые будут предшествовать и' на следующей итерации, находится текущая вершина и (согласно строке 11) и либо больше таких вершин нет (если и подвергалась подъему), либо там находятся те же вершины, что и ранее (если высота и не изменялась). Поскольку и подверглась разгрузке„она не содержит избытка потока.
Следовательно, если и подвергалась подъему в процессе разгрузки, то ни одна вершина, предшествующая и', не содержит избытка потока. Если же высота и в процессе разгрузки не менялась, ни одна вершина, стоящая в списке Ь перед ней, не получила избыток потока при этой разгрузке, поскольку Ь остается топологически упорядоченным все время в процессе разгрузки (как уже отмечалось, допустимые ребра создаются толью подъемами, а не операциями проталкивания), поэтому каждая операция проталкивания заставляет избыток потока двигаться только к вершинам, расположенным в списке дальше (или же к а или т). В этом случае ни одна вершина, предшествующая и', также не имеет избытка потока. Завершение. Когда цикл завершается, и оказывается за последним элементом списка Ь, поэтому инвариант цикла гарантирует, что избыток всех вершин равен О.
Следовательно, ни одна основная операция неприменима. Глава 26. Задача о максимальном потоке 783 ь: х, у л. х з Рис. 26.10. Работа процедуры Ка.яви. То г конт. Справа показан список Ь, где пол каждой вершиной приведен список ее соседей, в котором выделена текущая вершина Анализ Покажем теперь, что процедура Кн.яви. То рконт выполняется за время О (Ъ'з) для любой сети С = (У, Е). Поскольку данный алгоритм является реализацией универсального алгоритма проталкивания предпотока, воспользуемся следствием 26.22, которое устанавливает границу О (У) для числа подъемов, применяемых к одной вершине, и О (Уз) для общего числа подъемов.
Кроме того, в упражнении 26.4-2 устанавливается граница О (У Е) для суммарного времени, затраченного на выполнение подъемов, а лемма 26.23 устанавливает границу О (У Е) для суммарного числа операций насыщающих проталкиваний. Часть Ч1 Алгоритмы для работы с графами 784 у (~ з т х к, т х х х "у~~ ' 20~ Теорема 26.31. Времявыполненияпроцедуры КньАвнь То Рномтдлялюбойсе- ти С = (1', Е) составляет О (1'з). Доказатвельсвтво. Будем считать "фазой" алгоритма "поднять-в-начало" время между двумя последовательными операциями подъема.
Поскольку всего выполняется О (Ъ'з) подъемов, в алгоритме насчитывается О (Ъ'з) фаз. Каждая фаза сдержит не более Щ обращений к процедуре ПшснАксн, что можно показать следующим образом. Если процедура Рыснлксн не выполняет подъем, то следующий ее вызов происходит ниже по списку Ь, а длина Ь меньше ~Ц. Если процедура 1нзснАкпн выполняет подъем, то следующий ее вызов происходит уже в другой фазе алгоритма. Поскольку каждая фаза содержит не более ~Ц обращений к процедуре П~зснлксн и в алгоритме насчитывается О (Ъ'~) фаз, число вызовов данной процедуры строкой 8 процедуры Килвн. То Рком' составляет О (Ъ'~).Таким образом, цикл ип11е процедуры Кньлвн. То Ркслчт выполняет работу (не учитывая работу, выполняемую внутри процедуры П1вснлксп), не превышающую О (Ъ'з). Теперь необходимо оценить работу, выполняемую внутри процедуры П~зснАкпп в ходе выполнения данного алгоритма.
Каждое выполнение цикла тчЬ!1е в процедуре П[зснАкпн заключается в выполнении одного из трех действий. Проанализируем объем работы при выполнении каждого из них. Начнем с подъемов (строки 4-5). В упражнении 26.4-2 время для выполнения всех О (Ъ'з) подъемов ограничивается пределом О (У Е). Глава 26. Задача о максимальном потоке 785 Теперь предположим, что действие заключается в обновлении указателя ситтепг [и) в строке 8.
Это действие выполняется 0 (дебгее(и)) в том случае, когда вершина и подвергается подъему, что для всех вершин составляет 0(Ъ" !1ейгее(и)) раз. Следовательно, для всех вершин общий объем работы по перемещению указателей в списке соседей составляет 0((ГЕ) согласно лемме о рукопожатиях (упражнение Б.4-1). Третий тип действий, выполняемых процедурой Р!зснАкОе, — операция проталкивания (строка 7). Как уже отмечалось, суммарное число насьпцающих операций проталкивания составляет 0 (Ъ' Е). Если выполняется ненасышающее проталкивание, процедура ь1!ЕснАкОе немедленно выполняет возврат, поскольку такое проталкивание уменьшает избыток до О.
Поэтому при каждом обращении к процедуре Р!зснАеое может выполняться не более одного ненасыщающего проталкивания. Процедура Р!зснАкОе вызывается 0 (!'з) раз, следовательно, общее время, затраченное на ненасыщающие проталкивания, составляет О (!'з). Таким образом, время выполнения процедуры КВЕАВеь ТО РеОнт составляет 0 (1~2 + Ъ'Е), что эквивалентно 0 (Ъ'з). Упражнения 26.5-1. Проиллюстрируйте (используя в качестве образца рис.
26.10) выполнение процедуры КВЕАвеь ТО РЕОнт для сети, представленной на рис. 26.1а. Предполагается, что начальный порядок следования вершин в списке Š— (с1, с2, сз, с4), а списки соседей имеют следующий внд: Ж[и1) = (а,сз)сз), Ф [52) = (3) 01 э сз, с4), )1Г [сз) (с1 ~ с2 ~ е4 ~ 2) 1 1!( [с4) (с21 пз з !) ° *26.5-2. Мы хотим реализовать алгоритм проталкивания предпотока, в котором поддерживается порядок обслуживания переполненных вершин "первым вошел, первым вышел'".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
