Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 171
Текст из файла (страница 171)
Применив лемму 26.4, получаем, что (Д = У(Еи(а), Л0(8)) = !М~. ° На основании леммы 26.9 можно сделать вывод о том, что максимальное паросочетание в двудольном графе С соответствует максимальному потоку в соответствующей ему транспортной сети С', следовательно, можно находить максимальное паросочетание в С с помощью алгоритма поиска максимального потока в С'. Единственной проблемой в данных рассуждениях является то, что алгоритм поиска максимального потока может вернуть такой поток в С', в котором некоторое значение 1(и,э) оказывается нецелым, несмотря на то что величина ф должна быть целой.
В следующей теореме показано, что при использовании метода Форда-Фалкерсона такая проблема возникнуть не может. Теорема 26.10 1'Теорема о иелочислеииости1 Если функция пропускной способности с принимает только целые значения, то максимальный поток 1', полученный с помощью метода Форда-Фалкерсона, обладает тем свойством, что значение потока ф является целочисленным.
Более того, для всех вершин и и с величина 1(п, с) является целой. 774 Часто ГХ Алгоритмы дла работы с графами Доказавгельсвгво. Доказательство проводится индукцией по числу итераций. Его предлагается выполнить в качестве упр. 26.3.2. Теперь мы можем доказать следствие из леммы 26.9. Следсгв вне гб. 11 Мощность максимального паросочетания М в двудольном графе С равна вели- чине максимального потока 1 в соответствующей транспортной сети С'. Доказавгельсвгво. Воспользуемся терминологией леммы 26.9.
Предположим, что М представляет собой максимальное паросочетание в С, но соответствующий ему поток 1 в С' не максимален. Тогда в С' существует максимальный поток 1', такой, что ~~'~ > ф. Поскольку пропускные способности в С' являются целочисленными, теорема 26.10 позволяет считать поток 1' целочисленным. Таким образом, 1' соответствует некоторому паросочетанию М' в С мощностью ~М'! = ~~'( > ф = (М(, что противоречит нашему предположению о том, что М является максимальным паросочетанием. Аналогично можно показать, что если 1 — максимальный поток в С', то соответствующее ему паросочетание является максимальным паросочетанием в С. Таким образом, для заданного неориентированного двудольного графа С можно найти максимальное паросочетание путем создания транспортной сети С', применения метода Форда-Фалкерсона и непосредственного получения максимального паросочетания М по найденному максимальному целочисленному потоку 1.
Поскольку любое паросочетание в двудольном графе имеет мощность не более пйп(Ь, В) = 0(17), величина максимального потока в С' составляет 0(Ъ'). Поэтому максимальное паросочетание в двудольном графе можно найти за время 0(1гЕ') = 0(Ъ'Е), поскольку ~Е'~ = гз(Е). Упражнения гйз1 Примените алгоритм Форда-Фалкерсона для транспортной сети на рис. 26.8,(в) и покажите остаточную сеть после каждого увеличения потока. Вершины из множества Ь пронумеруйте сверху вниз от 1 до 5, а вершины множества Я вЂ” от 6 до 9. Для каждой итерации укажите лексикографически наименьший увеличивающий путь. газ.г Докажите теорему 26.10.
гб.з.з Пусть С = (17,Е) представляет собой двудольный граф с разбиением вершин 17 = ь ь1 Л, а С~ — соответствующая ему транспортная сеть. Найдите верхнюю границу длины любого увеличивающего пути„найденного в С' в процессе выполнения процедуры Ропп-Еь ькпкюм. Глава 2д Задача о максаиальпаи потоке 115 26.3.4 * Идеальное ларосочвтание (реггес! ша!сЬ(ля) представляет собой паросочетание, в котором каждая вершина является связанной. Пусть С = ((Г, Е) является неориентированным двудольным графом с разбиением вершин $' = Е1ЗВ, где Щ = ~В~.
Для любого Х С $' определим вкргслвнпсшь (пе1яЬЬогЬоов() Х как 1ч'(Х) = (у Е (Г: (з, у) б Е для некоторого х Е Х), т.е. это множество вершин, смежных с какой-либо из вершин Х. Докажите лвеорему Холла (На!Гз !Ьеогеш): идеальное паросочетание в С существует тогда и только тогда, когда )А! < ))ч'(А)) для каждого подмножества А С Е, 2б.3.5 * Двудольный граф С = (1',Е), где (Г = Е ГЗ Л, называется в1-регулярным (в(- гейл!аг), если каждая вершина о Е (Г имеет степень, в точности равную е(.
В каждом И-регулярном двудольном графе выполняется соотношение Щ = (Л~. Докажите, что в каждом И-регулярном двудольном графе имеется паросочетание мощности ~Е~, показав, что минимальный разрез соответствующей транспортной сети имеет пропускную способность !Х,1 * 26.4. Алгоритмы проталкивания предпотока В данном разделе будет рассмотрен подход к вычислению максимальных потоков, основанный на "проталкивании предпотока". В настоящее время многие асимптотически наиболее быстрые алгоритмы поиска максимального потока принадлежат данному классу, и на этом методе основаны реальные реализации алгоритмов поиска максимального потока.
С помощью методов проталкивания пред- потока можно решать и другие связанные с потоками задачи, например задачу поиска потока с минимальной стоимостью. В данном разделе приводится разработанный Голдбергом (бо14Ьегя) "обобщенный" алгоритм поиска максимального потока, для которого существует простая реализация с временем выполнения 0(Ъ'зЕ), что лучше времени рабаты алгоритма Эдмондса-Карпа О('йЕз). В разделе 26.5 данный обобщенный алгоритм будет усовершенствован, что позволит получить алгоритм проталкивания предпотока, время выполнения которого составляет 0(Г з).
Алгоритмы проталкивания предпотока работают способом, более локальным, чем метод Форда-Фалкерсона. Вместо того чтобы для поиска увеличивающего пути анализировать всю остаточную сеть, алгоритмы проталкивания предпотока обрабатывают вершины по одной, рассматривая только соседей данной вершины в остаточной сети. Кроме того, в отличие от метода Форда — Фалкерсона, алгоритмы проталкивания предпотока не обеспечивают поддержание в процессе работы свойства сохранения потока.
При этом, однако, они поддерживают лредлолвок (ргейози), который представляет собой функцию 3': Ъ' х (Г -+ !к, удовлетво- Часть й. Алгоритмы длл работы с графита 77б ряющую ограничениям пропускной способности и следующему ослабленному условию сохранения потока: ~До,ц) — 7 7(и,е) > О об к для всех вершин и Е 17 — (а). Будем называть величину е(и) = ~ 7'(о, п) — ~ ~7'(ц, е) (26.14) избыточным потоком (ехсезз йоьо), входящим в вершину и. Избыток в вершине представляет собой величину, на которую входящий поток превышает исходящий. Мы говорим, что вершина п Е 1' — (а,1) варепалиевная (очегйоичпя), если е(и) ) О. Мы начнем данный раздел с описания интуитивных соображений, приводящих к методу проталкивания предпотока. Затем рассмотрим две применяемые в данном методе операции: "проталкивание" предпотока и подъем (перемаркировка — ге1аЪе!шя) некоторой вершины.
Наконец, мы представим обобщенный алгоритм проталкивания предпотока н проанализируем его корректность и время выполнения. Интуитивные соображения Интуитивные соображения, лежащие в основе метода проталкивания предпотока, лучше всего проиллюстрировать на примере потоков жидкости: пусть транспортная сеть С = (17, Е) представляет собой систему труб с заданными пропускными способностями. Применив данную аналогию, о методе Форда-Фалкерсона можно сказать, что каждый увеличивающий путь в сети вызывает дополнительный поток жидкости без точек ветвления, который течет от истока к стоку.
Метод Форда-Фалкерсона многократно добавляет дополнительные потоки до тех пор, пока дальнейшее добавление станет невозможным. В основе обобщенного алгоритма проталкивания предпотока лежат другие интуитивные соображения. Пусть, как и ранее, ориентированные ребра соответствуют трубам. Вершины, в которых трубы пересекаются, обладают двумя интересными свойствами. Во-первых, чтобы принять избыточный поток, каждая вершина снабжена выходящей трубой, ведущей в произвольно большой резервуар, способный накапливать жидкость. Во-вторых, каждая вершина, ее резервуар и все трубные соединения находятся на платформе, высота которой увеличивается по мере работы алгоритма.
Высота вершины определяет, как протаякиваегся поток: поток может протачн кнваться только вниз, т.е. от более высокой вершины к более низкой. Поток может быть направлен и от нижестоящей вершины к вышестоящей, но операции проталкивания потока проталкивают его только вниз. Высота истока является фиксированной и составляет ~Ц, а фиксированная высота стока равна О. Высота всех других вершин сначала равна О и увеличивается со временем. Алгоритм сначала Плова 26. Задача о максимальном лошаке 777 посылает максимально возможный поток вниз от истока к стоку.
Посылается количество„в точности достаточное для заполнения всех выходящих из истока труб до достижения их пропускной способности; таким образом посылается поток, равный пропускной способности разреза (и, К вЂ” (в)). Когда поток впервые входит в некоторую транзитную вершину, он накапливается в ее резервуаре. Отсюда он со временем проталкивается вниз. Может случиться так, что все трубы, выходящие из вершины и и еще не заполненные потоком, ведут к вершинам, которые лежат на одном уровне с и или находятся выше нее. В этом случае, чтобы избавить переполненную вершину и от избыточного потока, необходимо увеличить ее высоту — провести операцию подъема (ге1аЪе1шя) вершины и. Ее высота увеличивается и становится на единицу больше, чем высота самой низкой из смежных с ней вершин, к которым ведут незаполненные трубы.
Следовательно, после подъема вершины существует по крайней мере одна выходящая труба, по которой можно протолкнуть дополнительный поток. В конечном итоге весь поток, который может пройти к стоку, оказывается там. Больше пройти не может, поскольку трубы подчиняются ограничениям пропускной способности; количество потока через любой разрез ограничено его пропускной способностью. Чтобы сделать предпоток "нормальным" потоком, алгоритм после этого посылает избытки, содержащиеся в резервуарах переполненных вершин, обратно к истоку, продолжая менять метки вершин, чтобы их высота превышала фиксированную высоту истока !171 Как будет показано, после того как резервуары окажутся пустыми, предпоток станет не только нормальным, но и максимальным потоком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
