Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 158
Текст из файла (страница 158)
В строке 3 вычисляется значение Иу (и, э), после чего в строках 4-5 обновляется 7", а в строках 6-7 обновляется е. Таким образом, если функция 7" являлась предпотоком перед вызовом процедуры Рази, она останется предпотоком и после ее выполнения.
Обратите внимание, что в коде процедуры РОЗН ничто не зависит от высот вершин и и и; тем не менее, мы запретили вызов процедуры, если не выполнено условие Ь [и] = Ь [э] + 1. Таким образом, избыточный поток проталкивается вниз только при разности высот, равной 1. Согласно лемме 26.13, между двумя вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер, а значит, поскольку атрибут Ь является функцией высоты, мы ничего не добьемся, разрешив проталкивать вниз поток при разности высот, превышающей 1. Процедура Рйьн(и, и) называется проталкиванием (риз1з) из и к и. Если операция проталкивания применяется к некоторому ребру (и, и), выходящему из вершины и, будем говорить, что операция проталкивания применяется к и. Если в результате ребро (и, и) становится насыщенным (зашгагед) (после проталкивания с7 (и, и) = 0), то зто насыщающее нроталкивание (за1игайпй риз1з), в противном случае это ненасыщающее проталкивание (попзашгайпд ризй).
Если ребро насыщено, оно не входит в остаточную сеть. Один из результатов ненасыщающего проталкивания характеризует следующая лемма. Лемма 26.14. После ненасыщающего проталкивания из и в и вершина и более не является переполненной. Доказательство. Поскольку проталкивание ненасыщающее, количество посланного потока должно быть равно величине е [и] непосредственно перед проталкиванием. Поскольку избыток е [и] уменьшается на зту величину, после проталкивания он становится равным О. Часть Ч!. Алгоритмы для работы с графами 766 Операция подъема Основная операция КеьлвеЦи) применяется, если вершина и переполнена и й [и] < л [и] для всех ребер (и, и) е Ег. Иными словами, переполненную вершину и можно подвергнуть подъему, если все вершины и, для которых имеется остаточная пропускная способность от и к э, расположены не ниже и, так что протолкнуть поток из и нельзя. (Напомним, что по определению ни источник а, ни сток т не могут быть переполнены; следовательно, ни з, ни т нельзя подвергать подъему.) Кн.лвн.(и) 1 1> Условия применения: и переполнена и для всех и Е г' таких что (и, и) е Е1, Ь[и] < !т[и).
2 ~> Действие: увеличивает высоту и. 3 Ю ~- 1+ ш!и (l [и): (и и) Е Е1) Когда вызывается операция Кеьлвеь(и), мы говорим, что вершина и подвергается иадьеыу (те!аЬе!ед). Заметим, что когда производится подъем и, остаточная сеть Ег должна содержать хотя бы одно ребро, выходящее из и, чтобы минимизация в коде операции производилась по непустому множеству. Это свойство вытекает из предположения, что вершина и переполнена. Поскольку е [и) > О, имеем е [и) = ! (У,и) > О и, следовательно, должна существовать по крайней мере одна вершина и, такая что 7" [и, и] > О.
Но тогда с1 (ии) = с(ил) — 7 [и,и] = с(ии) + у [ни) > О, откуда вытекает, что (и, и) е Еу. Таким образом, операция Кн.лвн.(и) дает и наибольшую высоту, допускаемую наложенными на функцию высоты ограничениями. Универсальный алгоритм Универсальный алгоритм проталкивания предпотока использует следующую процедуру для создания начального предпотока в транспортной сети: 11Ч!Т!ЛНЕЕ РКЕЕ1.0ту(С, а) 1 !ог (для) каждой вершины и Е Ъ'[С] 2 оо 6[и] — О 3 е[и) — О 4 1ог (для) каждого ребра (и, и) Е Е[С) 5 г1о Г" [и, и] — О б Ли>и] О 7 и[а] — ['г' [С]] 8 1ог (для) каждой вершины и Е Аф[а) Глава 26.
Задача о максимальном потоке Процедура 11ч1т1Ашге Рнег~.отч(С, в) создает начальный предпоток 2", определяемый формулой (26.10) То есть каждое ребро, выходящее из источника в, заполняется до его пропускной способности, а все остальные ребра не несут потока. Для каждой вершины и, смежной с источником, начальное значение е [и] = с (з, и), а начальное значение е [в) устанавливается равным сумме этих значений с обратным знаюм.
Универсальный алгоритм начинает работу с начальной функцией высоты [Ц еслии=в, 6[и) = 0 в противном случае. Это действительно функция высоты, поскольку единственными ребрами (и,и), для которых й [и] > Ь [и] + 1, являются ребра, для которых и = з, и эти ребра заполнены, а это означает, что их нет в остаточной сети. Инициализация, за которой следует ряд операций проталкивания и подьема, выполняемых без определенного порядка, образует алгоритм Ое1чек1с Рпзн КЕ1.АВЕ1.: бе1чен1с Р11зн КеьАви.(С) 1 1%Т!АШЕЕ РКЕЕЬ01Ч(С, з) 2 иЫ1е существует применимая операция проталкивания или подъема 3 Йо выбрать операцию проталкивания или подъема и выполнить ее Следующая лемма утверждает, что до тех пор пока существует хотя бы одна переполненная вершина, применима хотя бы одна из этих операций. Лемма 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 выполняются только операции проталкивания и подъема. Операции подъема влияют только на атрибуты высоты, но не на величины потока, следовательно, от них не зависит„будет ли г" предпотоком. Анализируя работу процедуры Ризн, мы доказали, что если Г является предпотоком перед выполнением операции проталкивания, он остается предпотоюм и после ее выполнения. Завершение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
