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