Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 173
Текст из файла (страница 173)
Ь никогда не уменьшается. Более того, всякий раз, когда к вершине и применяется операция подъема, ее высота и. Ь увеличивается как минимум на 1. Доказательство. Поскольку высота вершины меняется только при выполнении операции подъема, достаточно доказать второе утверждение леммы. Если вершина и должна подвергнуться подъему, то для всех вершин и, таких, что (и,и) Е Е(, выполняется условие и.Ь < и.Ь.
Таким образом, и. Ь < 1+ ппп (и. Ь; (и, и) Е Е( ), и операция должна увеличить значение и. Ь. ° Лемма 2б.16 Пусть С = (Ъ; Е) представляет собой транспортную сеть с истоком в и стоком Ь Во время выполнения процедуры Спннис-Рсзн-йн.лпн. над сетью С атрибут Ь сохраняет свойства функции высоты. Доказатееьство. Доказательство проводится индукцией по числу выполненных основных операций. Изначально, как уже отмечалось, Ь является функцией высоты. Мы утверждаем, что если Ь является функцией высоты, то операция Кн.лвн.(и) оставляет Ь функцией высоты.
Если рассмотреть остаточное ребро (и,и) Е Е1, которое выходит из и, то операция Кн.лпн.(и) гарантирует, Часть П. Алгоритмы для работы с графачи 7с2 что после нее будет выполняться соотношение и. Ь < и. Ь+ 1. Теперь рассмотрим остаточное ребро (и, и), входящее в и. Согласно лемме 26.15 из и. Ь < и. Ь + 1 перед выполнением операции КвьлввЦи) вытекает гс. Ь < и. Ь + 1 после нее. Таким образом, операция Квьлввь(и) оставляет Ь функцией высоты. Теперь рассмотрим операцию Рцзн(и, и). Эта операция может добавить ребро (и,и) к Ег, и может удалить ребро (и,и) из Ег. В первом случае имеем и. Ь = и.
Ь вЂ” 1 < и. Ь + 1, так что Ь остается функцией высоты. Во втором случае удаление ребра (и, и) из остаточной сети приводит к удалению соответствующего ограничения, так что Ь по-прежнему остается функцией высоты. ° Следующая лемма характеризует важное свойство функций высоты. Лемма 26.17 Пусть С = (1г, Е) представляет собой транспортную сеть с истоком з и стоком 1, 1 является предпотоком в С, а Ь вЂ” функцией высоты, определенной на множестве 1'. Тогда в остаточной сети Сг не существует пути из истока з в сток т.
Доказательство. Предположим, что в С1 имеется некоторый путь р = (ио, щ, ..., гь) из з в ~, где ио = з, а гь = г, и покажем, что это приводит к противоречию. Без потери общности можно считать, что р — простой путь, так что /с < ~Ц. Для 1 = О, 1,..., Ь вЂ” 1 ребра (иц и,,.~) Е Ег. Поскольку Ь является функцией высоты, для г = О, 1,,/с — 1 справедливы соотношения Ь(и,) < Ь(и,~з) + 1.
Объединив эти неравенства вдоль пути р, получаем, что Ь(з) < Ь(г) + Ь. Но поскольку Ь(1) = О, получаем Ь(е) < Ь < ~Ъ'(, что противоречит требованию Ь(з) = ~Ц к функции высоты. Теперь мы готовы показать, что после завершения обобщенного алгоритма проталкивания предпотока вычисленный алгоритмом предпоток является максимальным потоком. Теорема 26.18 (Корректность обобщенного алгоритма проталкнеання предпотока) Если алгоритм Овнвк1с-Рцзн-Квьлввь, выполняемый над транспортной сетью С = (Ъ; Е) с истоком е и стоком г, завершается, то вычисленный им предпоток 1 является максимальным потоком в С, Доказагпельстео.
Воспользуемся следующим инвариантом цикла. Всякий раз, когда в строке 2 процедуры Овмвкк-Рцзн-Квьлввь выпол- няется проверка условия цикла зтЫ1е, У является предпотоком. Инициализации. 1н1т1Ашхв-Рквн.оц' делает 1 предпотоком. Сохранение. Внутри цикла зеЫ!е в строках 2 и 3 выполняются только операции проталкивания и подъема.
Операции подъема влияют только на атрибуты высоты, но не на величины потока, следовательно, от них не зависит, будет ли ) предпотоком. Анализируя работу процедуры Рцзн, мы доказали (с. 778), что Глава Зд Задача о максимальном нотоке 7бЗ если З является предпотоком перед выполнением операции проталкивания, он остается предпотоком и после ее выполнения. Завершение. По завершении процедуры каждая вершина из множества 17 — (в, г) должна иметь нулевой избыток, поскольку из леммы 26.14 и инварианта, что 7" всегда остается предпотоком, вытекает, что переполненных вершин нет.
Следовательно, 7" является потоком. Лемма 26.16 показывает, что при завершении Ь является функцией высоты; таким образом, согласно лемме 26.17 в остаточной сети СЗ не существует пути из в в г. Согласно теореме о максимальном потоке и минимальном разрезе (теорема 26.6) У является максимальным потоком. Анализ метода проталкивания предпотока Чтобы показать, что обобшенный алгоритм проталкивания предпотока действительно завершается, найдем границу количества выполняемых им операций.
Для каждого вида операций (подъем, насышаюшее проталкивание и ненасышаюшее проталкивание) имеется своя граница. Зная эти границы, несложно построить алгоритм, время работы которого — 0(17зЕ). Однако, прежде чем проводить анализ, докажем важную лемму. Вспомним, что мы разрешаем ребрам входить в исток в остаточной сети. ллемма 36.19 Пусть С = (К Е) представляет собой транспортную сеть с истоком в и стоком г, а 7" является предпотоком в С.
Тогда в остаточной сети СЗ для любой переполненной вершины х существует простой путь из х в в. Доиоалвельсвиво. Для переполненной вершины х введем У = (и: существует простой путь из х в и в СГ). Теперь предположим, что б ф У, и покажем, что это приводит к противоречию. Обозначим (7 = 17 — У. Возьмем определение избытка из уравнения (26.14), выполним суммирование по всем вершинам в У и заметим, что 17 = У 0 (7.
Это даст е(и) о«П 7 (и, и) — ~~~ 1(и, и) о«п «ь' о«и 7(и,и) + ~~~ З(и,и) — ~~~ З'(и,и) + ~~~ Г(и,и) о«п «и о«Г' «и о«Г З(и, и) + ~~~ ~~~ Г(и, и) — ~ ~~~ 7'(и, и) — ~~~ ~~~ 7(и, и) о«У о«У о«п «и о«п «и «и «и 7(и, и) — ~~~ ~~~ 1(и, и) . о«п «и о«п «и Часть И. Алгоритмы для работы с графами 7в4 Мы знаем, что величина ~„„епе(и) должна быть положительной, поскольку е(х) > О, х б У, что все вершины, отличные от в, имеют неотрицательный избыток и что согласно нашему предположению в ф 17. Таким образом, имеем р 1(и,и) — ~ ~ 1(и,и) > О. (26.
17) меп еи мс77 ьвт7 Все потоки ребер неотрицательны, так что, чтобы выполнялось уравнение (26.17), необходимо иметь ~„„ег7 2, — 1(и, и) > О. Следовательно, должна существовать как минимум одна пара вершин и' н У и и' е Г, обладающих тем свойством, что 1(и', и') > О.
Но если 1(и', и') > О, должно существовать остаточное ребро (и', и'), а зто означает, что имеется простой путь из х в и' (путь х и' — ~ и'), что противоречит определению У. В следующей лемме устанавливаются границы высот вершин, а в вытекающем из нее следствии устанавливается предел общего числа выполненных операций подъема. Л 2й20 Пусть С = (17, Е) представляет собой транспортную сеть с истоком в и стоком г.
В любой момент в процессе выполнения процедуры Окнкк!с-Рпзн-Кньлвн. над сетью С для всех вершин и е 17 выполняется соотношение и. Ь < 2 ~Ц вЂ” 1. Доказательство. Высоты истока в и стока 1 никогда не изменяются, поскольку эти вершины по определению не переполняются. Таким образом, всегда ж Ь = Щ и 1. Ь = О, причем оба значения не превышают 2 ٠— 1. Рассмотрим теперь произвольную вершину и Н 17 — (в,1). Изначально и.
Ь = О < 2 ٠— 1. Покажем, что после каждого подъема неравенство и. Ь < 2 ٠— 1 остается справедливым. При подъеме вершины и она является переполненной, и согласно лемме 26.19 имеется простой путь р из и в в в С1. Пусть р = (ио, иы ..., иь), где ио = и, гь = в и /с < 1Ц вЂ” 1, поскольку р — простой путь. Для 1 = 0,1,...,/с — 1 имеем (и;,и,4.1) е Е1, а следовательно„иоЬ < и,~1.Ь + 1 согласно лемме 26.16. Расписав неравенства для всех составляющих пути р, получаем и Ь = ио Ь < иы Ь + /с < в Ь + (~17) — 1) = 2 (Ц вЂ” 1. Следствие 26.21 (йерхппй предел числа подъемоа1 Пусть С = (Ъ; Е) представляет собой транспортную сеть с истоком в и стоком 1. Тогда в процессе выполнения процедуры Окнккн>РОзн-КкьАвдг. над С чис- ло подъемов не превышает 2 ~Ц вЂ” 1 на вершину, а их общее количество — не более (2 ~Ц вЂ” 1)(~Ц вЂ” 2) < 2 Щ . Доказательство.
В множестве 17 — (в,г) могут быть подняты только )Ц вЂ” 2 вершин. Пусть и е $' — (в,1). Операция Ккьлвн.(и) увеличивает высоту и.Ь. Значение и. Ь изначально равно 0 и согласно лемме 26.20 возрастает не более чем до 2 ~Ц вЂ” 1. Таким образом, каждая вершина и Е 17 — (в,т) подвергается Гявю 2д Задача о квтимальнам яотот 785 подъему не более 2 ~Ц вЂ” 1 раз, а общее число выполненных подъемов не превы- шает (2 )Ц вЂ” 1)()Ц вЂ” 2) < 21Ц . Лемма 26.20 помогает также определить границу количества насыщающих проталкиваний.
Лемма 26.22 ~Граница количества насыщающих нроталкнваннй) В процессе выполнения алгоритма Опмнис-рпзн-Кн.яви. нал любой транспортной сетью С = ($7,Е) число насыщающих проталкиваний меньше, чем 2)Ц )Е(. Доказательство. Для любой пары вершин и, и е Ъ' рассмотрим насыщающие проталкивания от и к и и от и к и (в обе стороны) и назовем их насыщающими проталкиваниями между и и и.
Если есть хотя бы одно такое проталкивание, то хотя бы одно из ребер (и, и) и (и, и) является ребром из Е. Теперь предположим, что произошло насыщающее проталкивание из и в и. В этот момент и. Ь = и. Ь вЂ” 1. Чтобы позднее могло произойти еще одно проталкивание из и в и, алгоритм сначала должен протолкнуть поток из и в и, что невозможно до тех пор, пока не будет выполнено условие и. Ь = и. Ь + 1. Поскольку и. Ь никогда не уменьшается, для того чтобы выполнялось условие и. Ь = и. Ь + 1, значение и. Ь должно увеличиться по меньшей мере на 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
