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