Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 159
Текст из файла (страница 159)
По завершении процедуры каждая вершина из множества У вЂ” (а, г) должна иметь избыток, равный О, поскольку из лемм 26. !5 и 26. !7 и инварианта, что Г всегда остается предпотоком, вытекает, что переполненных вершин нет. Следовательно, г является потоком. Поскольку Ь вЂ” функция Часть У1. Алгоритмы для работы с графами 770 высоты, согласно лемме 26.18 не существует пути из в в т в остаточной сети Су. Согласно теореме о максимальном потоке и минимальном разрезе (теорема 26.7), г" является максимальным потоком. 1 Анализ метода проталкивания предпотока Чтобы показать, что универсальный алгоритм проталкивания предпотока действительно завершается, найдем границу числа выполняемых им операций. Для каждого вида операций (подъем, насыщающее проталкивание и иенасыщающее проталкивание) имеется своя граница.
Зная эти границы, несложно построить алгоритм, время работы которого О (к з Е). Прежде чем проводить анализ, докажем важную лемму. Лемма 26.20. Пусть С = (К Е) — транспортная сеть с источником в и стоком 1, а Г" — предпоток в С. Тогда для любой переполненной вершины и существует простой путь из и в в в остаточной сети Су. е(У) = г" (У, У) = = У(й,У)+У(У,У) = =У(й,У) <О (из уравнения (26.9)) (согласно лемме 26.1 (часть 3)) (согласно лемме 26.1 (часть 1)). Излишки неотрицательны для всех вершин из множества У вЂ” (в); поскольку мы предположили, что У С 1г — (в), то для всех вершин и е У должно выполняться е (и) = О. В частности, е (и) = О, что противоречит предположению о том, что и переполнена.
И Следующая лемма устанавливает границы высот вершин, а вытекающее из нее следствие устанавливает предел общего числа выполненных операций подъема. Доказвигельсигво. Пусть и — некоторая переполненная вершина, и пусть У = (о: в Су существует простой путь из и в и). Предположим, что в (с У, и покажем, что это приведет нас к противоречию. Обозначим У = У вЂ” У. Утверждается, что для каждой пары вершин ю Е У и и Е У выполняется соотношение г" (ю,и) < О.
Почему? Если г'(то,и) > О, то г" (и,ш) ( О, откуда в свою очередь вьпекает, что су (и, и) = с(и, то) — 7" (и, и) > О. Следовательно, существует ребро (и, гл) Е Еу и существует простой путь вида и -» и — ~ ю в остаточной сети Сг, что противоречит тому, как мы выбирали и. Таким образом, должно выполняться неравенство Г" (У, У) < О, поскольку каждое слагаемое в зтом неявном суммировании неположительно, и, следовательно, Глава 26. Задача о максимальном потоке Лемма 2621.
Пусть С = (К Е) — транспортная сеть с источником з и стоюм Ь В любой момент в процессе выполнения процедуры Оемещс Ризи Кн.Авн. в сети С для всех вершин и е 1' выполняется соотношение Ь [и] < 2 ٠— 1. Доказаогезьсшво. Высоты источника з и стока 1 ниюгда не изменяются, посюльку эти вершины по определению не переполняются. Таким образом, всегда Ь [з] = = Щ и Ь [Ф] = О, и обе не превышают 2 ٠— 1. Рассмотрим теперь произвольную вершину и Е Ъ вЂ” (з, г). Изначально Ь [и] = = 0 < 2 [Ъ'[ — 1.
Покажем, что после каждого подъема неравенство Ь [и] < 2[1'[ — 1 остается справедливым. При подъеме вершины и она является переполненной и, согласно лемме 26.20, имеется простой путь р из и в з в С1. Пусть р = = (ио,им...,иь), где ил = и, а из = з, и Й < [Ц вЂ” 1, поскольку р — простой путь. Для 1 = О, 1,..., Ь вЂ” 1 имеем (ип и;+1) Е Еу, следовательно, Ь [и;] < Ь [и,+1] + + 1 согласно лемме 26.17. Расписав неравенства для всех составляющих пути р, получаем Ь [и] = Ь [ив] < Ь [ил]+ /с < Ь[в]+ (٠— 1) = 2[1'[ — 1.
Следствие 26.22 (Верхний предел числа падъемов). Пусть С = (К Е) транспортная сеть с источниюм з и стоком ~. Тогда в процессе выполнения процедуры Ончещс Рцзн Кн.Авн. в С число подъемов не превышает 2[Ц вЂ” 1 для одной вершины, а их общее количество не более (2 [Ц вЂ” 1) ([Ц вЂ” 2) < 2 [1'[~. Доказательсогво. Во множестве У вЂ” (з,1) только [Ц вЂ” 2 вершин могут быть подняты. Пусть и Е У вЂ” (з, $). Операция КЕЬАВЕЬ(и) увеличивает высоту Ь [и].
Значение Ь [и] первоначально равно 0 и, согласно лемме 26.21, возрастает не более чем до 2 [Ц вЂ” 1. Таким образом, каждая вершина и Е Ъ'- (з, г) подвергается подьему не более 2 [Ц вЂ” 1 раз, а общее число выполненных подъемов не превышает (2[1'[ — 1) ([1'[ — 2) < 2[Ц .
Лемма 26.21 помогает также определить границу юличества насыщающих проталкиваний. Лемма 26.23 (Граница количества насыщающих проталкиваний). В процессе выполнения алгоритма Оекек~с Рпзн КеьАееь для любой транспортной сети С = (Р; Е) число насыщающих проталкиваний меньше, чем 2[У[[Е[. Доказашезьсигво. Для любой пары вершин и,и Е Ъ' рассмотрим насыщающие проталкивания от и к и и от и к и (в обе стороны), и назовем их насыщающими проталкиваниями между и и и. Если есть хотя бы одно такое проталкивание, то хотя бы одно из ребер (и, и) и (и, и) является ребром Е. Теперь предположим, что произошло насыщающее проталкивание из и в и.
В этот момент Ь [и] = Ь [и]— — 1. Чтобы позднее могло произойти еше одно проталкивание из и в и, алгоритм сначала должен протолкнуть поток из и в и, что невозможно до тех пор, пока не Часть Ч!. Алгоритмы для работы с графами 772 будет выполнено условие Ь [и) = Ь [и) + 1. Поскольку Ь [и) никогда не уменьшается, для того чтобы выполнялось условие Ь [и) = Ь [и] + 1, значение Ь [и) должно увеличиться по меньшей мере на 2.
Аналогично, Ь [и] должно увеличиться между последовательными насыщающими проталкиваниями из и в и как минимум на 2. Высота изначально принимает значение О и, согласно лемме 26.21, никогда не превышает 2 ($'( — 1, откуда следует, что количество раз, когда высота вершины может увеличиться на 2, меньше (Ц. Поскольку между двумя насыщающимя проталкиваниями между и и и хотя бы одна из высот Ь [и) и Ь [и] должна увеличиться на 2, всего имеется меньше 2(Ц насыщающих проталкиваний между и и и.
Умножив это число на число ребер, получим, что общее число насыщающих проталкиваний меньше, чем 2 Щ (Е(. й Следующая лемма устанавливает границу числа ненасышающих проталкиваний в обобщенном алгоритме проталкивания предпотока. Лемма 26.24 !Граница количества ненасыщающих проталкиваний). В процессе выполнения алгоритма Овчнк!с Рази Кпьлвнь для любой транспортной сети С = [Ъ; Е) число ненасыщающих проталкиваний меньше 4 (Ц~ [(Ц + (Е(). Доказатявльсигво.
Определим потенциальную функцию Ф = ~"„.,О,1>о Ь [и]. Изначально Ф = О и значение Ф может изменяться после каждого подъема, насыщающего и ненасыщающего проталкивания. Мы найдем предел величины, на которую насыщающие проталкивания и подъемы могут увеличивать Ф. Затем покажем, что каждое ненасыщающее проталкивание должно уменьшать Ф как минимум на 1, и используем эти оценки для определения верхней границы числа ненасышающих проталкиваний.
Рассмотрим два пути увеличения Ф. Во-первых, подъем вершины и увеличивает Ф менее чем на 2 Щ, поскольку множество, для которого вычисляется сумма, остается прежним, а подъем не может увеличить высоту вершины и больше, чем ее максимально возможная высота, которая составляет не более 2 (Ц вЂ” 1 согласно лемме 26.21. Во-вторых, насыщающее проталкивание из вершины и в вершину и увеличивает Ф менее чем на 2 (Ц„поскольку никаких изменений высот при этом не происходит, и только вершина и„высота которой не более 2 (Ц вЂ” 1, может стать переполненной. Теперь покажем, что ненасыщающее проталкивание из и в и уменьшает Ф не менее чем на 1. Почему? Перед ненасыщающим проталкиванием вершина и была переполненной, а и могла быть переполненной или непереполненной. Согласно лемме 26.14, после этого проталкивания и больше не является переполненной.
Кроме того, после данного проталкивания и должна быть переполненной, если только она не является источником. Следовательно, потенциальная функция Ф уменьшилась ровно на Ь (и]„а увеличилась на О или на Ь (и]. Поскольку Ь [и)— — Ь [и] = 1, в итоге потенциальная функция уменьшается как минимум на !.
Глава 26. Задача о максимальном потоке Итак, в ходе выполнения алгоритма увеличение Ф происходит благодаря подъемам и насыщающим проталкиваниям; согласно следствию 26.22 и лемме 26.23, это увеличение ограничено, и составляет менее (21У~) (2 Щ ) + +(2(Ц) (2~Ц (Е!) = 4 Щ~((У1+ )Е!). Поскольку Ф > О, суммарная величина уменьшения и, следовательно, общее число ненасыщаюших проталкиваний меньше, чем 4 Щ~ ()Ц + (Е().
И Определив границу числа подъемов, насыщающего проталкивания и ненасыщающего проталкивания, мы заложили основу дальнейшего анализа процедуры бнчиыс Ризн КиьАввь, а также любых других алгоритмов, основанных на методе проталкивания предпотока. Теорема 26.25. При выполнении процедуры Оечеис Ризи КеьАвнь для любой транспортной сети С = (У, Е) число основных операций составляет О (УвЕ). Доказалгельслюво. Непосредственно вытекает из уже доказанных следствия 26.22 и лемм 26.23 и 26.24. Таким образом, алгоритм завершается после О (УзЕ) операций.
Итак, осталось предложить эффективные методы реализации каждой операции и выбора подходящей выполняемой операции. Следствие 26.26. Существует реализация обобщенного алгоритма проталкивания предпотока, которая для любой сети С = (У, Е) выполняется за время О (У2Е) Доказательство. В упражнении 26.4-1 предлагается показать, как реализовать обобщенный алгоритм, в котором на каждый подъем затрачивается время О (У), а на каждое проталкивание — О (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
