Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 170
Текст из файла (страница 170)
всего не более ~Ъ7~ /2 раз. Поскольку в остаточном графе имеется 0(Е) пар вершин, которые могут быть соединены ребрами в остаточной сети, общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно 0(ЪГЕ). Каждый увеличивающий путь содержит по крайней мере одно критическое ребро„а значит, теорема доказана. Поскольку, если использовать поиск в ширину, можно выполнять каждую итерацию процедуры Гокп-Гпькккзом за время 0(Е), общее время работы алгоритма Эдмондов — Карпа оказывается равным 0(ЪГЕз). Мы покажем, что алгоритмы проталкивания предпотока позволяют достичь еще лучших результатов. На основе алгоритма из раздела 26.4 построен метод, который позволяет достичь времени выполнения 0(ЪГЭЕ); этот метод является основой алгоритма со временем выполнения 0(Ъ'з), рассматриваемого в разделе 26.5. Уирвкненив 26.2.2 Докажите, что сумма в уравнении (26.6) равна сумме в уравнении (26.7).
гй2.2 Чему равен поток через разрез ((а,оз,ол), (емоз,г)) на рис.26.1,(б)? Какова пропускная способность этого разреза? 26.2.5 Продемонстрируйте выполнение алгоритма Эдмондса-Карпа на примере транс- портной сети, представленной на рис. 26.1, (а). 26.2.4 Укажите на рис. 26.6 минимальный разрез, соответствующий показанному максимальному потоку. Какой из показанных в примере увеличивающих путей приводит к сокращению потока? 26.25 Вспомним предложенную в разделе 26.1 конструкцию, которая преобразует транспортную сеть с несколькими истоками и несколькими стоками в сеть с одним истоком и одним стоком путем добавления ребер с бесконечной пропускной способностью.
Докажите, что любой поток в полученной сети имеет конечную величину, если ребра исходной сети с множественными истоками и стоками имеют конечную пропускную способность. 26.2. 6 Предположим, что каждый исток а, в задаче с множественными истоками и стоками производит ровно р, единиц потока, так что,) „к /(а,, о) = ро Предположим также, что каждый сток 1, потребляет ровно ЛЭ единиц, так что ~ „як /(о, 17) =?о, М Зьк. З7М 770 Чдсти Рб Алгоритмы длл работы с грабами где ~''г р; = ~„1 д .
Покажите, как преобразовать данную задачу поиска потока 1, удовлетворяющего указанным дополнительным ограничениям, в задачу поиска максимального потока в транспортной сети с одним истоком и одним стоком. 26.2. 7 Докажите лемму 26.2. 26.2.8 Предположим, что мы переопределили остаточную сеть, запретив ребра, входяшие в л. Докажите, что процедура Гоко-Гпькккзом все равно будет корректно вычислять максимальный поток.
26.2.9 Предположим, что и 7, и 1' являются потоками в сети С и что мы вычисляем поток 1"? 1'. Будет ли увеличенный поток удовлетворять свойству сохранения потока? А ограничению пропускной способности? 26.2.1б Покажите, как найти максимальный поток в сети С = (У, Е) путем последовательности не более чем из ~ Е~ увеличиваюших путей. (Указаниег определите пути восле нахождения максимального потока.) 26.2.11 Реберной связностью (ебйе соплесйийу) неориентированного графа называется минимальное число ребер к, которые необходимо удалить, чтобы разъединить граф. Например, реберная связность дерева равна 1, а реберная связность циклической цепи вершин равна 2. Покажите, как определить реберную связность неориентированного графа С = (У, Е) с помощью алгоритма максимального потока не более чем для Щ транспортных сетей, каждая из которых содержит 0(У) вершин и 0(Е) ребер.
26.2.12 Предположим, что имеется транспортная сеть С и что в С имеются ребра, входяшие в исток ж Пусть 1 представляет собой поток в С, в котором одно из входящих в исток ребер (и, л) имеет Де, з) = 1. Докажите, что должен существовать другой поток ~' с ~'(е,з) = О, такой, что ф = )~'~. Разработайте алгоритм со временем работы 0(Е), который вычисляет ~' по данному 7', в предположении, что все пропускные способности ребер являются целыми числами. 26.2.13 Предположим, что вам требуется найти среди всех минимальных разрезов транспортной сети С с целочисленными пропускными способностями тот, который содержит наименьшее количество ребер. Покажите, как изменить пропускные способности С, чтобы создать новую транспортная сеть С', в которой любой минимальный разрез в С' является минимальным разрезом с наименьшим количеством ребер в С.
77! !лава 2б. Задача а макаанальнаа аатаке 26.3. Максимальное паросочетаиие Некоторые комбинаторные задачи можно легко свести к задачам поиска максимального потока. Одной из таких задач является задача определения максимального потока в сети с несколькими истоками и стоками, описанная в разделе 26.1. Существуют другие комбинаторные задачи, которые, на первый взгляд, имеют мало общего с транспортными сетями, однако могут быть сведены к задачам поиска максимального потока.
В данном разделе рассматривается одна из подобных задач: поиск максимального паросочетания в двудольном графе. Чтобы решить данную задачу, воспользуемся свойством полноты, обеспечиваемым методом Форда-Фалкерсона. Мы также покажем, что с помогцью метода ФордаФалкерсона можно решить задачу поиска максимального паросочетания в двудольном графе С = (Ъ; Е) за время 0(Ъ'Е). Задача поиска максимального паросочетаиия в двудвльном графе Пусть дан неориентированный граф С = (К Е). Паросочетаннеи (ша1сЬ(п8) называется подмножество ребер М С Е, такое, что для всех вершин о е Ъ' в М содержится не более одного ребра, инцидентного о.
Мы говорим, что вершина о е $' является связанной (шагсЬед) паросочетанием М, если в М есть ребро, инцидентное о; в противном случае вершина о называется открытой (цпша!сЬеб). Максимольньин пороеочетанием называется паросочетание максимальной мощности, т.е. такое паросочетание М, что для любого паросочегания М' справедливо соотношение ~М( > ~М'(. В данном разделе мы ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах, т.е.
в графах, множество вершин которых можно разбить на два подмножества 1' = Е О Л, где Е и Л не пересекаются и все ребра в Е проходят между Е и й. Далее мы предполагаем, что каждая вершина в Г имеет по крайней мере одно инцидентное ребро. Понятие паросочетания проиллюстрировано на рис. 26.8. Задача поиска максимального паросочетания в двудольном графе имеет множество практических приложений.
В качестве примера можно рассмотреть паросочетание множества машин Ь и множества задач Н, которые должны выполняться одновременно. Наличие в Е ребра (и, о) означает, что машина и е Е может выполнять задачу о е Е. Максимальное паросочетание обеспечивает максимальную загрузку машин. Поиск максимального парасочетания в двудольном графе С помощью метода Форда — Фалкерсона можно найти максимальное паросочетание в неориентированном двудольном графе С = (К, Е) за время, полиномиально зависящее от 1г'1 и 1Е!. Фокус заключается в том, чтобы построить транспортную сеть, потоки в которой соответствуют паросочетаниям, как показано на рис. 26.8, (в). Определим для заданного двудольного графа С соответстауюнгую транспортную сеть С' = (Г, Е') следующим образом.
Возьмем в качестве истока з и стока 1 новые вершины, не входяшие в $', и положим Ъ" = $' О (е, г). Часть Ьу. Алгоритмы алл работы с графами (ь) (в) Рззс. 26.6. Двудольный зраф сь = ((г, Е) с разбиением вершин Р = Ь 0 й. (а) Пщюсочегаиие с мощностью 2 (ребра выделены штриховкой).
(6) Максимальное паросачетание с мощностью 3. (в) Саответствующал транспартнал сеть С' с показанным максимальным потоком. Каждое ребро имеет единичную пропускную способность. Через заштрихованные ребра идет поток величиной ц во всех остальных ребрах потока нет. Заштрихованные ребра из Ь в гь соответствуют заштрихованным ребрам в максимальном паросочетании в части (6). Если разбиение вершин в графе С представляет собой $' = Х О В, ориентированными ребрами С' являлися ребра Е, направленные из Х в Л, а также ~Ц новых ориентированных ребер Е' = ((л, и): и т Х) 0 ((и, и): (и, и) т Е) О ((и,(): и е В) Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность. Поскольку каждая вершина из множества вершин 1' имеет по крайней мере одно инцидентное ребро, )Е~ > ) Ц /2.
Таким образом, )Е! < ) Е'~ = )Е!+ )Ц < 3)Е), так что Щ = тт(Е). Следующая лемма показывает, по паросочетание в С непосредственно соответствует потоку в соответствующей транспортной сети С'. Поток Х в транспортной сети С = (К, Е) называется целочисленным (ш(ейег-ча)пей), если значения Х(и, и) целые для всех (и, и) б. Ъ' х 1'. Л гбр Пусть С = ((г, Е) является днудольным графом с разбиением вершин 1' = Х О гт и пусть С' = ((гР, Е') представляет собой соответствующую ему транспортную сеть. Если М является паросочетанием в С, то существует целочисленный поток Х в С', величина которого — Щ = )М~. Справедливо и обратное утверждение: если Х представляет собой целочисленный поток в С', то в С существует паросочетанне М с мощностью )М~ = ф. Докпзплнельсшвлх Покажем сначала, что паросочетанню М в графе С соответствует некоторый целочисленный поток У в сети С'.
Определим У следующим образом. Если (и, е) е М, то Х(л, и) = Х(и, и) = Х(п, () = 1. Для всех остальных 773 Глава еб. Задача а макеимапьпам потоке ребер (и, с) Е Е' определим 1" (и, с) = О. Нетрудно убедиться, что 1 удовлепюряет ограничению пропускной способности и сохранению потока. Интуитивно понятно, что каждое ребро (и, с) Е М соответствует единице потока в С', проходящего по пути я -+ и — > с -+ 1. Кроме того, пути, порожденные ребрами из М, представляют собой непересекающиеся множества вершин, не считая а и 1. Чистый поток через разрез (Ь |.1 (а), В 11 (1)) равен )М(; следовательно, согласно лемме 26.4 величина потока равна ф = )М). Чтобы доказать обратное, предположим, что 1 — некоторый целочисленный поток в С', и пусть М=((пс):и ЕЕ, сб1в, и1(и,ц) )О) Клждая вершина и е Ь имеет только одно входящее ребро, а именно — (я, и), и его пропускная способность равна 1. Следовательно, в каждую вершину и е Ь входит не более одной единицы положительного потока, и если она действительно входит, то из нее должна также выходить одна единица положительного потока согласно свойству сохранения потока.
Более того, поскольку 1' — целочисленный поток, для каждой вершины и е Ь одна единица потока может входить не более чем по одному ребру и выходить не более чем по одному ребру. Таким образом, одна единица положительного потока входит в и тогда и только тогда, когда существует в точности одна вершина с Е В, такая, что 1'(и, с) = 1, и из каждой вершины и е Б выходит не более одного ребра, несущего положительный поток. Симметричные рассуждения применимы для каждой вершины с е Л. Следовательно, М является паросочетанием. Чтобы показать, что (М! = (Д, заметим, что 1(а, и) = 1 для кюкдой связанной вершины и б Е, и для каждого ребра (и, с) ŠŠ— М мы имеем 1'(и, с) = О. Следовательно, 1(Ь0(з), 1ь0(г)), чистый поток через разрез (1 0(а),Я0(г)), равен )М!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
