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