Алгоритмы - построение и анализ (1021735), страница 156
Текст из файла (страница 156)
Задача о максимальном потоке М вЂ” паросочетание в С, то существует целочисленный поток г' в С', величина которого Щ = (М(. Справедливо и обратное утверждение: если ~ — целочисленный поток в С', то в С существует паросочетание М с мощностью )М! = )Д. Доказаюиельство. Покажем сначала, что паросочетанию М в графе С соответствует некоторый целочисленный поток Г" в сети С'. Определим Г следующим образом. Если (и,е) Е М, то Г" (з,и) = Г" (и,о) = Г" (е,1) = 1 и Г" (и,з) = Г" (е,и) = Г" (1,п) = -1. Для всех остальных ребер (и,о) Е Е' определим Г" (и, о) = О. Нетрудно убедиться, что г" обладает свойством антисимметричности, удовлетворяет ограничениям пропускной способности и сохранения потока.
Интуитивно понятно, что каждое ребро (и, о) Е М соответствует единице потока в С', проходящего по маршруту а — и ~ о — 8. Кроме того, пути, порожденные ребрами из М, представляют собой непересекающиеся множества, не считая а и т. Чистый поток через разрез (Ь О (а),ВО (8)) равен (М); следовательно, согласно лемме 2б.5, величина потока равна (Я = (М!. Чтобы доказать обратное, предположим, что г" — некоторый целочисленный поток в С', и пусть М = ((и, о): и е Ь, е е В и г (и, о) ) О) .
Каждая вершина и Е Ь имеет только одно входящее ребро, а именно (з, и), и его пропускная способность равна 1. Следовательно, в каждую вершину и Е Ь входит не более одной единицы положительного потока, и если она действительно входит, то из нее должна также выходить одна единица положительного потока согласно свойству сохранения потока. Более того, поскольку Г' — целочисленный поток, для каждой вершины и Е Ь одна единица потока может входить не более чем по одному ребру и выходить не более чем по одному ребру.
Таким образом, одна единица положительного потока входит в и тогда и только тогда, когда существует в точности одна вершина не В, такая что г" (и, и) = 1, и из каждой вершины ие ь выходит не более одного ребра, несущего положительный поток. Симметричные рассуждения применимы для каждой вершины о Е Я.
Следовательно, М является паросочетанием. Чтобы показать, что )М( = Щ, заметим, что 1 (а, и) = 1 для каждой связанной вершины и Е Ь, и Г" (и, о) = О для каждого ребра (и, о) ŠŠ— М. Следовательно, ~М~ = Г (Ь, В) = Г" (Ь, У') — Г (Ы,) — Г" (Ь, а) — 1 (Ь, 1) согласно лемме 2б.!. Приведенное выражение можно значительно упростить. Из свойства сохранения потока следует, что г (Ь, Г) = О; из леммы 26.1 следует, что г" (Ы,) = О; согласно свойству антисимметричности, -г" (Ь, а) = г" (а, Ь); и поскольку нет ребер, Часть Ч1. Алгоритмы для работы с графами 760 ведущих из Ь к г, 2" (Ь, й) = О.
Таким образом, (поскольку все ребра, выходящие из а, идут в Ь) (согласно определению Щ). На основании леммы 26.10 можно сделать вывод, что максимальное паросочетание в двудольном графе С соответствует максимальному потоку в соответствующей ему транспортной сети С', следовательно, можно находить максимальное паросочетание в С с помощью алгоритма поиска максимального потока в С'. Единственной проблемой в данных рассуждениях является то, что алгоритм поиска максимального потока может вернуть такой поток в С', в котором некоторое значение 1 (и, о) оказывается нецелым, несмотря на то, что величина Щ должна быть целой. Следующая теорема показывает, что такая проблема не может возникнуть при использовании метода Форда-Фалкерсона. Теорема 26.11 (Теорема о целочисленности).
Если функция пропускной способности с принимает только целые значения, то максимальный поток 1', полученный с помощью метода Форда-Фалкерсона, обладает тем свойством, что значение потока ~Я является целочисленным. Более того, для всех вершин и и э величина Г" (и, ю) является целой. Доказалгельслыо. Доказательство проводится индукцией по числу итераций. Его предлагается провести в качестве упражнения 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 портная сеть С = (К Е) представляет собой систему труб с заданными пропускными способностями. Применяя данную аналогию, о методе Форда-Фалкерсона можно сказать, что каждый увеличивающий путь в сети вызывает дополнительный поток жидкости, без точек ветвления, который течет от источника к стоку. Метод Форда-Фалкерсона многократно добавляет дополнительные потоки, пока дальнейшее добавление станет невозможным. В основе обобщенного алгоритма проталкивания предпотока лежат другие интуитивные соображения. Пусть, как и ранее, ориентированные ребра соответствуют трубам. Вершины, в которых трубы пересекаются, обладают двумя интересными свойствами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
