Алгоритмы - построение и анализ (1021735), страница 158
Текст из файла (страница 158)
Лемма 26.15 (Для переполненной вершины можно выполнить либо проталкивание, либо подъем). Пусть С = (У, Е) — транспортная сеть с источником в и стоком 1, 1 — предпоток, а Ь вЂ” неюторая функция высоты для 1. Если и— некоторая переполненная вершина, то к ней можно применить или операцию проталкивания, или операцию подъема. 9 10 11 12 йо Г[з,и] — с(в,и) 1[и, в] — — с(з, и) е[и) +- с(в, и) е[з) +- е[в] — с(в, и) с(и,и) ,Г [и,и] = — с(и,и) 0 еслии=з, если и = з, в противном случае.
Часть Ч1 Алгоритмы для работы с графами 768 Доказалгельстео. Для любого остаточного ребра (и, и) выполняется соотношение Ь (и) < Ь (и)+1, посюльку Ь вЂ” функция высоты. Если к и не применима операция проталкивания, то для всех остаточных ребер (и, и) должно выполняться условие Ь (и) < Ь (и) + 1, откуда следует, что Ь(и) < Ь(и). В этом случае к и можно применить операцию подъема. Корректность метода проталкивания предпотока Чтобы показать, что универсальный алгоритм проталкивания предпотока позволяет решить задачу максимального потока, сначала докажем, что после его завершения предпоток Г является максимальным потоком.
Затем докажем, что алгоритм завершается. Начнем с рассмотрения некоторых свойств функции высоты Ь. Лемма 26.16 (Высота вершины никогда не уменьшается). При выполнении процедуры бвнвис Рнзн Ки.лвн. над транспортной сетью С = (1г, Е), для любой вершины и е 1г ее высота Ь [и] никогда не уменьшается. Более того, всякий раз, когда к вершине и применяется операция подъема, ее высота Ь [и] увеличивается как минимум на 1. Доказательство. Посюльку высота вершины меняется толью при выполнении операции подъема, достаточно доказать второе утверждение леммы. Если вершина и должна подвергнуться подъему, то для всех вершин и, таких что (и, и) е Ег, выполняется условие Ь [и] < Ь [и]. Таким образом, Ь [и] < 1 + ппп(Ь [и]: (и, и) е Е Еу), и операция должна увеличить значение Ь [и]. И Лемма 26.17. Пусть С = (1г, Е) — транспортная сеть с источником з и стоком С Во время выполнения процедуры бвнвюс Рнзн Кв.лвн.
над сетью С атрибут Ь сохраняет свойства функции высоты. Доказательсгяво. Доказательство проводится индукцией по числу выполненных основных операций. Как уже отмечалось, вначале Ь является функцией высоты. Утверждается, что если Ь вЂ” функция высоты, то после выполнения операции Квьлввь(и) она останется функцией высоты.
Если посмотреть на остаточное ребро (и, и) е Еу, выходящее из и, то операция Ки.лви.(и) гарантирует, что после ее выполнения Ь [и] < Ь [и] + 1. Рассмотрим теперь некоторое остаточное ребро (из, и), входящее в и. Согласно лемме 26.16, Ь [ш] < Ь [и] + 1 перед выполнением операции Кн.лви.(и); следовательно, после ее выполнения Ь [и] < Ь [и] + 1.
Таким образом, операция КБ.Ава.(и) оставляет Ь функцией высоты. Теперь рассмотрим операцию Рнвн(и, и). Данная операция может добавить ребро (и, и) к Е1 или удалить ребро (и, и) из Еу. В первом случае имеем Ь [и] = = Ь [и] — 1 < Ь [и] + 1, так что Ь остается функцией высоты. Во втором случае Глава 26. Задача о максимальном потоке 769 удаление ребра (и, е) из остаточной сети приводит к удалению соответствующего ограничения, так что Ь по-прежнему остается функцией высоты.
Следующая лемма характеризует важное свойство функций высоты. Лемма 26.18. Пусть С = (К Е) — транспортная сеть с источником з и стоком 1, г' — предпоток в С, а Ь вЂ” функция высоты, определенная на множестве У. Тогда не существует пути из источника а к стоку ! в остаточной сети Су. Доказагаельсгиво. Предположим, что в Су существует некоторый путь р = (со, ен ..., оь) из з в 1, где ео = з, а еь = 1, и покажем, что это приводит к противоречию. Без потери общности можно считать, что р — простой путь, так что Й < Щ.
Для ! = 0,1,..., Ь вЂ” 1, ребра (ен гч+г) б Еу. Посюльку Ь вЂ” функция высоты, для ! = О, 1,..., Ь вЂ” 1 справедливы соотношения Ь (га) < Ь (с;+1) + 1. Объединяя эти неравенства вдоль пути р, получим, что Ь (а) < Ь (1) + Ь. Но поскольку Ь (!) = О, получаем Ь (з) < Ь < Щ, что противоречит требованию Ь (з) = )Ц к функции высоты.
Теперь покажем, что после завершения универсального алгоритма проталкивания предпотока вычисленный алгоритмом предпоток является максимальным потоком. Теорема 26.19 (О корректности универсального алгоритма проталкивания предпотока). Если алгоритм Овнвк!с Ризн Кн.Авва, выполняемый над сетью С = (К Е) с источником з и стоком 1, завершается, то вычисленный им предпоток 1 является максимальным потоком в С. Доказательство.
Мы используем следующий инвариант цикла: Всякий раз, когда производится проверка условия цикла згЫ!е в строке 2 процедуры Овнвкк Рнзн КвьАвн., г" является предпотоком. Инициализация. Процедура 1н!т[лщгк Рквн.ов делает 7" предпотоком. Сохранение. Внутри цикла иЫ!е в строках 2-3 выполняются только операции проталкивания и подъема. Операции подъема влияют только на атрибуты высоты, но не на величины потока, следовательно, от них не зависит„будет ли г" предпотоком. Анализируя работу процедуры Ризн, мы доказали, что если Г является предпотоком перед выполнением операции проталкивания, он остается предпотоюм и после ее выполнения. Завершение.
По завершении процедуры каждая вершина из множества У вЂ” (а, г) должна иметь избыток, равный О, поскольку из лемм 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 (Верхний предел числа падъемов). Пусть С = (К Е) транспортная сеть с источниюм з и стоком ~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
