Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 172
Текст из файла (страница 172)
Основные операции Как следует из предыдущих рассуждений, в алгоритме проталкивания пред- потока выполняются две основные операции: проталкивание избытка потока от вершины к одной из соседних с ней вершин и подъем вершины. Применение этих операций зависит от высот вершин, которым мы сейчас дадим более точные определения. Пусть С = (17, Е) представляет собой транспортную сеть с истоком в и стоком г, а З является некоторым предпотоком в С. Функция )з: 17 -+ 1й является функцией высояиы (Ье)яЬ! Пзпс()оп), )г(в) = !17(, )з(г) = О и Ь(и) < )з(о)+1 для каждого остаточного ребра (и,тг) е Е~.
Сразу же можно сформулировать следующую лемму. зв лншрятуре функпия высоты обычно незымегся функцией ресшояния (жзеиже йшсйоп), е высоте вершины нвзывштся мепвзй рвсстояния (жнвпсе !вье!). Мы используем термин "высоте", посюльку он лунце соглвсуется с интуитивным обосноввнием алгоритма. Высоте вершины связенв с ее расстоянием от стока Г, иморое можно найти с помошью поиске в ширину в ьгт. Часть Ку. Алгоритмы для работы с графами 77В Л гб.уг Пусть С = (17, Е) представляет собой транспортную сеть, а / является некоторым предпотоком в С, и пусть Ь вЂ” функция высоты, заданная на множестве И. Для любых двух вершин и, о е 1' справедливо следующее утверждение: если Ь(и) > Ь(о) + 1, то (и, о) не является ребром остаточной сети.
Операция проталкивания Основная операция РОЗН(и, о) может применяться тогда, когда и является переполненной вершиной, су(и, о) > О и Ь(и) = Ь(о) + 1. Представленный ниже псевдокод обновляет предпоток / и избыточный поток для и и о. Предполагается, что остаточные пропускные способности су(и, о) при заданных / и с можно вычислить за фиксированное время. Излишний поток в вершине и поддерживается в виде атрибута и, е, а высота вершины и — в виде атрибута и.Ь. Выражение уеду(и, о) представляет собой временную переменную, в которой хранится количество потока, которое можно протолкнуть из и в о.
РОЗН(и, о) 1 // Применяется при: вершина и переполнена, // су(и, о) > О и и. Ь = о. Ь + 1. 2 // Действие: проталкивает азу(и,о) = ппп(и. е, су(и, о)) // единиц потока из и в о. 3 азу(и,о) = т1п(и, е, су(и,о)) 4 И'(и,о) Е Е 5 (и,о)./ = (и,о)./+ с1у(и,о) 6 е1яе (о,и)./ = (о,и)./ — сау(и,о) 7 и. е = и. е — с) у(и, о) 8 о, е = о.
е + Ьу(и, о) Процедура Рнзн работает следующим образом. Поскольку вершина и имеет положительный избыток и.е и остаточная пропускная способность ребра (и,о) положительна, можно увеличить поток из и в о на величину у)ьу(и,о) ппп(и. е, су(и, о)), при этом избыток и. е не становится отрицательным и не будет превышена пропускная способность с(и,о). В строке 3 вычисляется значение с1у(и,о), после чего в строках 4 — 6 обновляется /.
В строке 5 увеличивается поток в ребре (и, о), поскольку мы проталкиваем поток через остаточное ребро. которое также является и исходным ребром. В строке 6 уменьшается поток в ребре (о, и), поскольку остаточное ребро в действительности обратно ребру в исхолной сети. Наконец в строках 7 и 8 обновляются избыточные потоки в вершины и и о.
Таким образом, если / являлся предпотоком перед вызовом процедуры Рнзн. он останется предпотоком и после ее выполнения. Обратите внимание, что в коде процедуры РОЗН ничто не зависит от высот вершин и и о; тем не менее мы запретили вызов процедуры, если не выполнено условие и. Ь = о. Ь + 1. Таким образом, избыточный поток проталкивается вниз только при разности высот, равной 1. Согласно лемме 26.12 между двумя вершинами, высоты которых отличаются более чем на 1, не сушествует остаточных 779 Глава ЗД Задача о маесамалвном вотоее ребер, а значит, поскольку атрибут Ь является функцией высоты, мы ничего не добьемся, разрешив проталкивать вниз поток при разности высот, превышающей 1.
Процедура Рцзн(и, и) называется проталкиванием (рпзЬ) из и в и. Если операция проталкивания применяется к некоторому ребру (и, и), выходящему из вершины и, будем говорить, что операция проталкивания применяется к и. Если а результате ребро (и, и) становится насыщенным (загшагед) (после проталкивания с/(и, и) = О), то это насыщающее проталкивание (зацпаг)пя рпзЬ), в противном случае это ненасыщающее проавалкивание (попзаппаг)пя рцзЬ). Если ребро становится насыщенным, оно исчезает из остаточной сети. Один из результатов ненасышаюшего проталкивания характеризует следующая лемма. Л гбв После ненасышаюшего проталкивания из и в и вершина и более не является переполненной.
Доказательство. Поскольку проталкивание ненасыщаюшее, фактическое количество посланного потока аь/(и, и) должно быть равно величине и. е непосредственно перед проталкиванием. Поскольку избыток и. е уменьшается на зту величину, после проталкивания он становится равным О. Операция подъема Основная операция Квълввь(и) применяется, если вершина и переполнена и если и. Ь < и. Ь для всех ребер (и, и) е Е/. Иными словами, переполненную вершину и можно подвергнуть подъему, если все вершины и, для которых имеется остаточная пропускная способность от и к и, расположены не ниже и, так что протолкнуть поток из и нельзя. (Напомним, что по определению ни исток в, ни сток Г не могут быть переполнены; следовательно, ни в, ни Г нельзя подвергать подъему.) Кн.лвн. (и) 1 // Применяется при: вершина и переполнена, и для всех и Е $', таких, // что(и,и) ~ Е/, имеем и.Ь < и.Ь.
2 // Деиствие: увеличивает высоту и. 3 и.Ь = 1+пни(и.Ь: (и,и) е Е/'1 Когда вызывается операция Кн.лвн.(и), мы говорим, что вершина и подвергается подъему (ге!аЬе!ед). Заметим, что когда выполняется подъем и, Е/ должно содержать хотя бы одно ребро, выходящее из и, чтобы минимизация в коде операции осуществлялась по непустому множеству.
Это свойство вытекает из предположения о том, что вершина и переполнена, что, в свою очередь, говорит нам, что и.с = ~/(и,и) — ~/(и,и) > О. чсу Поскольку все потоки неотрицательны, должна быть по крайней мере одна вершина и, такая, что (и,и)./ > О. Но тогда с/(и,и) > О, откуда вытекает, что Часть ст. Алгоритмы длл работы с графами 780 (и, с) е Е7.
Таким образом, операция йньАннь(н) назначает н наибольшую вы- соту, допускаемую наложенными на функцию высоты ограничениями. 1ЬПТ1АПЕЕ-РКЕН.ОЧ7(С, Л) 1 1ог каждой вершины с Е С. У 2 0.ЬиаО 3 е.еьаО 4 1ог каждого ребра (и, е) ~ С. Е 5 (н,о).1' = О 6 л.Ь = (С. 17~ 7 1ог каждой вершины с Е л. Аф 8 (з, 0).7 = с(л, е) 9 е.е = с(л,е) 10 л.е = з.е — с(л,о) 1н[т1Ащхн-Ркнгьоа создает начальный предпоток 7", определяемый как е (и, е), если н = з, О в противном случае . (26.15) Иначе говоря, каждое ребро, выходящее из истока л, заполняется до его пропускной способности, а все остальные ребра не несут потока.
Для каждой вершины о, смежной с истоком, изначально мы имеем с. е = с(л, с) и инициализируем л. е суммой этих значений с обратным знаком. Обобщенный алгоритм начинает работу с начальной функцией высоты Ь, задаваемой следующим образом: т ~Ц, если н = л, и.Ь = О в противном случае .
(26. 16) Уравнение (26.16) определяет функцию высоты, поскольку единственными ребрами (н, е), для которых и. Ь > е. Ь + 1, являются те, для которых и = з, и эти ребра заполнены, а это означает, что их нет в остаточной сети. Инициализация, за которой следует ряд операций проталкивания и подъема, выполняемых без определенного порядка, образует алгоритм Онннк10-РпзнйН.АВН.. Оехнк1с-РОБн-ин1.АВе1(С) 1 1спт!Ашхе-Ркен.0% (С, л) 2 зтЫ)е существует применимая операция проталкивания или подъема 3 выбрать и выполнить операцию проталкивания или подъема Обобщенный алгоритм Обобщенный алгоритм проталкивания предпотока использует следующую подпрограмму для создания начального предпотока в транспортной сети.
Глава зд Задача о макличальнач потоке В следующей лемме утверждается, что до тех пор, пока существует хотя бы одна переполненная вершина, применима хотя бы одна из этих операций. Лемма 2б.14 (Для переполненной вершном можно выполнить либо протелннванне, либо подъем) Пусть С = (К Е) представляет собой транспортную сеть с истоком в и стоком й а ( является предпотоком, и пусть Ь является произвольной функцией веса для (. Если и представляет собой произвольную переполненную вершину, то к ней применимо либо проталкивание, либо подъем. Доказательство.
Для любого остаточного ребра (и, и) выполняется соотношение Ь(и) < Ь(и) + 1, поскольку Ь представляет собой функцию высоты. Если к переполненной вершине и не применима операция проталкивания, то для всех остаточных ребер (и, и) должно выполняться условие Ь(и) < Ь(и) +1, откуда следует, что Ь(и) < Ь(и). В таком случае к и можно применить операцию подъема.
° Корректность метода проталкивании предпотока Чтобы показать, что обобщенный алгоритм проталкивания предпотока позволяет решить задачу максимального потока, сначала докажем, что если он завершается, то предпоток 1" является максимальным потоком. Затем докажем, что алгоритм завершается. Начнем с рассмотрения некоторых свойств функции высоты Ь. Лемма 2б.15 (Высота вершины никогда не уменьшается1 При выполнении процедуры Снннк1с-Рсзн-КпсАвпс над транспортной сетью С = (К, Е) для любой вершины и е Г ее высота и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
