Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 175
Текст из файла (страница 175)
Просуммировав зти равенства вдоль циклического пути, получаем Ь(и1 — 1) ~~ (Ь(иь) + 1) ь=1 1=1 Ь(и1) + Ь . Поскольку каждая вершина цикла р встречается при суммировании по одному разу, приходим к выводу, что О = Ь, что противоречит первоначальному предположению.
В двух следующих леммах показано, как операции проталкивания и подъема изменяют допустимую сеть. Л Л27 Пусть С = (17, Е) представляет собой транспортную сеть, )' — предпоток в С, и предположим, что атрибут Ь является функцией высоты. Если вершина и переполнена, а (и,и) является допустимым ребром, то применима процедура Рнзн(и,и). Эта операция не создает новых допустимых ребер, но может привести к тому, что ребро (и, и) станет недопустимым. Доюоательство. По определению допустимого ребра из и в и можно протолкнуть поток. Поскольку вершина и переполнена, применяется операция Р|ззн(и, и). В результате проталкивания потока из и в и может быть создано толью одно новое остаточное ребро (и, и). Поскольку и.
Ь = и. Ь вЂ” 1, ребро (и, и) не может стать допустимым. Если примененная операция является насыщающим проталкиванием, то после ее выполнения с)(и, и) = О и ребро (и, и) становится недопустимым. 790 Часть рь Алгоритмы длл работы с графами Лемма 26.28 Пусть С = (1; Е) представляет собой транспортную сеть, )' является предпотоком в С, и предположим, что атрибут Ь является функцией высоты.
Если вершина и переполнена и не имеется допустимых ребер, выходящих из и, то применяется операция Кн.лвн.(и). После подъема появляется по крайней мере одно допустимое ребро, выходящее из и, но нет допустимых ребер, входящих в и. Доказательство. Если вершина и переполнена, то согласно лемме 26.14 к ней применяется или операция проталкивания, или операция подъема. Если не сушествует допустимых ребер, выходяших из и, то протолкнуть поток нз и невозможно, следовательно, применяется операция Ккьлвкь(и).
После данного подьема и. Ь = 1+ ппп (о. Ь: (и, 0) Е Е1 ). Таким образом, если о — вершина, в которой реализуется минимум указанного множества, ребро (п,о) становится допустимым. Следовательно, после подъема имеется по крайней мере одно допустимое ребро, выходящее из и. Чтобы показать, что после подъема не существует входящих в и допустимых ребер, предположим, что существует некоторая вершина о, такая, что ребро (о, и) допустимо. Тогда после подъема о.
Ь = и. Ь + 1, так что непосредственно перед подъемом ш Ь > и. Ь + 1. Но согласно лемме 26.12 не существует остаточных ребер между вершинами, высоты которых отличаются более чем на 1. Кроме того, подъем вершины не меняет остаточную сеть. Таким образом, ребро (0, и) не принадлежит остаточной сети, а следовательно, оно не может находиться в допустимой сети. Списки соседей Ребра в алгоритме "поднять-в-начало" объединены в так называемые "списки соседей".
В заданной транспортной сети С = (й, Е) списком соседей (пе(яЬЬог !еп) и. Ф некоторой вершины п Е 1г является односвязный список вершин, смежных с ив С. Таким образом, вершина о оказывается в списке и.Ф, если (и,о) 6 Е или (0, и) Е Е. Список соседей и. гУ содержит только такие вершины о, для которых может существовать остаточное ребро (о,о). На первую вершину в списке и. Аг указывает указатель и.Ж. Ьеас(. Указатель о. пех1-пехуЬБот указывает на вершину, следующую в списке соседей за 0; этот указатель имеет значение ьпь, если о является последней вершиной в списке соседей. Алгоритм "поднять-в-начало" циклически обрабатывает каждый список соседей в произвольном порядке, который фиксируется в процессе выполнения алгоритма.
Для каждой вершины и атрибут и. сиггеп1 указывает на текущую вершину списка и. Ь'. Изначально и, сиггеп1 устанавливается равным и. М. Ьеай. Разгрузка переполненной вершины Переполненная вершина и лазгружаельсл (гйзсЬагдеб) путем проталкивания всего ее избыточного потока через допустимые ребра в смежные вершины, при этом, если необходимо, выполняется подъем вершины и, чтобы ребра, выходящие Глава Зб. Задача а макелмалькам катане 79! из вершины и, стали допустимыми.
Псевдокод разгрузки выглядит следующим образом. ьт!БСНАКСлЕ(и) 1 тлййеи.е >О 2 и = и.сигтепг 3 11'и == нп. 4 КеьАве1.(и) 5 и.сигтеп1 = и.тт'.Лесть 6 е1зеЫс7(и,и) > О ни.)т == и.6+1 7 Ризи(и, и) 8 е!яе и. сигтеп1 = и. пех1-петухе На рис. 26.9 показаны несколько итераций цикла твпйе (строки 1-8), тело которого выполняется до тех пор, пока вершина и имеет положительный избыток, Каждая итерация выполняет одно из трех действий в зависимости от текущей вершины и из списка соседей и. Ат. 1. Если и равно нть, значит, мы дошли до конца списка и.Ф. Выполняется подьем вершины и (строка 4), а затем (строка 5) текущей соседней вершиной и делается первая вершина из списка и.
Ат. (В лемме 26.29 утверждается, что в данной ситуации подъем применим.) 2. Если и не равно Н1Ь и ребро (и, и) является допустимым (что определяется с помощью проверки в строке 6), то (строка 7) выполняется проталкивание части (или всего) избытка из и в вершину и. 3. Если и не равно нп., но ребро (и, и) является недопустимым, то (строка 8) указатель и. ситтеп1 в списке и.
А7 перемещается на одну позицию вперед. Заметим, что если процедура ПтзснАнсе вызывается для некоторой переполненной вершины и, последним действием, выполняемым данной процедурой, должно быть проталкивание из и. Почему? Процедура завершается только тогда, когда избыток и. е становится равным нулю, и ни подъем, ни перемещение указателя и. ситгеп1 не влияют на значение и.
е. Теперь необходимо убедиться, что когда процедура ПтзснАкое вызывает процедуры Рнзн или КееАвее, эти операции применимы. В следующей лемме доказывается данный факт. Лемма 26.29 Если процедура ПщснАксе вызывает в строке 7 процедуру Ртззн(и,и), то к (и,и) применима операция проталкивания. Если процедура Птзснхкпе вызывает в строке 4 процедуру КеьАвеь(и), к вершине и применим подъем.
Доказалтельслтво. Проверки в строках 1 и 6 гарантируют, что операция проталкивания вызывается только тогда, когда она применима; таким образом, первое утверждение леммы доказано. 792 Часть ру. ллгаршлмы дия роботы с жьгФвии 5 4 (9) " 8 ~:" х* ьгь)рь~ ','В,) г з к х х (а) .с т 6 5 2 ~,л«5(~, У~ 5 6 7 (б) 8 9 э э х х (в) Рнс. 26.9. Рапрузка вершины р. Она требует 16 итераций цикла жййе процедуры Пщснлкпв для того, чтобы протолкнуть весь избыточный поток нз р. Показаны только соседи р и ребра транспортной сети, которые входят в вершину р или покидают ес. В каждой части рисунка число внутри вершины представляет собой ее избыток в начале первой итерации, показанной в данной части; кроме того, в пределах части каждая вершина показана на своей высоте. Список соседей р, )(( в начале каждой итерации приведен в правой части; в первой строке указан номер итерации.
Звшэриховвнным соседом явлжтся р. соггеп(. (а) Изначально имеется 19 единиц избытка, которые должны быль прстолкпугы из р, и р. сиггеп( = в. Итерации 1-3 просто обновляют значение у. сиггеп(, поскольку не имеется допустимых ребер, поющающих р. В итерации 4 р. сиггеп( = н)ь (уквзано штриховкой под списком соседей], так что у поднимается и р. сиггепэ сбрасываетсв, получая в качестве значения заголовок списка соседей. (6) После подъема высота вершины р равна 1.
В итерашщх 5 и 6 выясняегсл, что ребра (р, а) и (р, л) недопустимые, но в итерации 7 выполняетсл проталкивание 8 единиц избыточного потока из р в л. Из-за проталкивания в этой итерации значение у.сигтеп( не изменяется. (в) Поскольку проталкивание в итерации 7 насыщает ребро (у, з), в итерации 8 обнаруживается его недопустимость. В итерации 9 у.сютел( = шь, так что вершина р снова поднимается, а р. сиг геп( сбрасьгваеия. Рааса 2б. Зш)ачо о максимальном потоке 793 5 ч офл 4 1О х к (г) 12 13 14 з 3 х х г 15 я (е) (н) Рнс. 26Э (првдоллмнне). (г) В итерации 1О ребро (р,е) недопустимо, но нтерацня 11 проталкивает б еднннц нзбьпочного потока из р в к.
(д) Поскольку значение р. сигтел( не изменялось в итерации 11, в итерация 12 обнаруннвается, что ребро (р, ж) недопусппаое. Итерация 13 находит недопустимость ребра (р, х), а итерация 14 поднимает вершину р н сбрасывает значение р. сиггеп(. (е) Итерацги 15 проталкивает б единиц нзбьпочного потова нз р в а. (ш) Вершина р теперь не имеет избыточного потока, н процедура Вшсняксп завершается. В этом примере процедура ()(зснянап н начинается, и завершаетсв с текущим указателем на заголовок списка соседей, но в общем случае зто не обязательно так. Часть П.
Алгаритмы длл рабаты с графами 794 Чтобы доказать второе утверждение, исходя из проверки в строке 1 и леммы 26.28, необходимо только показать, что все ребра, выходящие из и, являются недопустимыми. если вызов РщснАкбе(и) начинается с указателем и.сиггепь на голову списка соседей, а по завершении он указывает за конец списка, то все выходящие из и ребра недопустимы, и применяется операция подъема. Возможно, однако, что во время вызова Ршснлкце(и) указатель и.ситтепг проходит только по части списка перед возвратом из процедуры. После этого могут произойти вызовы процедуры Рщснлксе с другими вершинами, но указатель и.
сиггепб будет перемещаться по списку в процессе следующего вызова РБзснАксе(и). Рассмотрим теперь, что произойдет при полном проходе по списку, который начинается с заголовка и.)Ч и заканчивается значением и. сиггепг = ып.. Когда и. сиггеМ достигает конца списка, процедура поднимает и и начинает новый проход. Чтобы в процессе прохода указатель и. ситтепб переместился за вершину и е и.
У, ребро (и,и) должно быть признано недопустимым проверкой в строке 6. Таким образом, к моменту завершения прохода каждое ребро, покидающее и, определено как недопустимое в некоторый момент этого прохода. Ключевым является тот факт, что к концу прохода все ребра, покидающие и, остаются недопустимыми. Почему? Согласно лемме 26.27 операции проталкивания не могут приводить к созданию допустимых ребер, независимо от того, из какой вершины выполняется проталкивание. Таким образом, любое допустимое ребро должно быть создано операцией подьема.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
