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