Алгоритмы - построение и анализ (1021735), страница 155
Текст из файла (страница 155)
Следовательно, за время, прошедшее с момента, когда ребро (и, и) было критическим, до момента, когда оно становится критическим в следующий раз, расстояние до и от источника увеличивается не менее чем на 2. Расстояние до и от Доказательство. Назовем ребро (и, и) остаточной сети Су критическим (спбса1) для увеличивающего пути р, если остаточная пропускная способность р равна остаточной пропускной способности ребра (и, и), т.е.
если су (р) = сг (и, и). После увеличения потока вдоль некоего увеличивающего пути, все критические ребра этого пути исчезают из остаточной сети. Кроме того, по крайней мере одно ребро любого увеличивающего пути должно быль критическим. Теперь покажем, что каждое из (Е( ребер может становиться критическим не более )Ц/2 — 1 раз. Пусть и и и — вершины из множества вершин У, соединенные некоторым ребром из множества Е.
Поскольку увеличивающие пути — это кратчайшие пути, то когда ребро (и, и) становится критическим первый раз, справедливо равенство Глава 26. Задача о максимальном потоке 755 источника в начальный момент было не меньше О. Среди промежуточных вершин на кратчайшем пути из а в и не могут находиться з, и или Г (поскольку наличие ребра (и, и) в кратчайшем пути подразумевает, что и ~ 1). Следовательно, к тому моменту, когда вершина и станет недостижимой из источника (если такое произойдет), расстояние до нее будет не более ~Ц вЂ” 2.
Таким образом, ребро (и, е) может стать критическим не более (٠— 2)/2 = ~Ъ"~/2 — 1 раз. Поскольку в остаточном графе имеется не более О (Е) пар вершин, которые могут быть соединены ребрами, общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно О (Ъ' Е). Каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно, теорема доказана. И Если увеличивающий путь находится посредством поиска в ширину, каждую итерацию процедуры рою Риьквкзом можно выполнить за время О(Е), следовательно, суммарное время выполнения алгоритма Эдмондса-Карпа составляет 0 (Р" Ез). Мы покажем, что алгоритмы проталкивания предпотока позволяют достичь еще лучших результатов. На основе алгоритма из раздела 26.4 построен метод, который позволяет достичь времени выполнения 0 (к'зЕ); этот метод является основой алгоритма со временем выполнения 0 ('к"з), рассматриваемого в разделе 26.5.
Упражнения 26.2-1. Чему равен поток через разрез ((а, оз, п4), (пы оз, г)) на рис. 26.16? Чему равна пропускная способность данного разреза? 26.2-2. Продемонстрируйте выполнение алгоритма Эдмондса-Карпа на примере транспортной сети, представленной на рнс. 26.!а. 26.2-3. Укажите минимальный разрез на рис. 26.5, соответствующий показанному максимальному потоку. Какие два из представленных в примере увеличивающих путей взаимно уничтожают поток? 26.2-4.
Докажите, что для любой пары вершин и, и и произвольных функций пропускной способности с и потока 7" справедливо соотношение сГ (и, е) + су (и, и) = с(и, п) + с(п, и). 26.2-5. Вспомним предложенную в разделе 26.1 конструкцию, которая преобразует транспортную сеть с несколькими источниками и несколькими стоками в сеть с одним источником и одним стоком путем добавления ребер с бесконечной пропускной способностью. Докажите, что любой поток в полученной сети имеет конечную величину, если ребра исходной сети с множественными источниками и стоками имеют конечную пропускную способность.
Часть Ч1. Алгоритмы для работы с графами 756 26.2-6. Предположим, что каждый источник ги в задаче со множественными источниками и стоками производит ровно р; единиц потока, так что ~ (а;, У) = р;. Предположим также, что кюкцый сток 1; потребляет ровно 93 единиц, так что Г" (У,1 ) = щ, где 2,'гр; = 2 9з. Покажите, как преобразовать данную задачу поиска потока г", удовлетворяющего указанным дополнительным ограничениям, в задачу поиска максимального потока в транспортной сети с одним источником и одним стоком. 26.2-7. Докажите лемму 26.3. 26.2-8.
Покажите, что максимальный поток в сети О = (У, Е) всегда можно найти с помощью последовательности не более чем из ~Е~ увеличивающих путей. (Указание: считая, что максимальный поток известен, покажите, как следует выбирать пути.) 26.2-9. Запасиег связиослги (едйе соппес11т11у) неориентированного графа назовем минимальное число ребер 1г, которые необходимо удалить, чтобы разъединить граф. Например, запас связности дерева равен 1, а запас связности циклической цепи вершин равен 2. Покажите, как определить запас связности неориентированного графа С = (У, Е) с помощью алгоритма максимального потока не более чем для Щ транспортных сетей, каждая из которых содержит О (У) вершин и О (Е) ребер.
26.2-10. Предположим, что транспортная сеть С = (У, Е) содержит симметричные ребра, т.е. (и, п) е Е тогда и только тогда, когда (е, и) е Е. Покажите, что алгоритм Эдмондса-Карпа завершается после не более чем ЩИЕ~у'4 итераций. (Указание: для произвольного ребра (и, и) проследите, как меняются б(а,и) и б(п,т) между последовательными моментами, когда ребро (и, е) становится критическим.) 26.3 Максимальное паросочетание Некоторые комбинаторные задачи можно легко свести к задачам поиска максимального потока. Одной из таких задач является задача определения максимального потока в сети с несколькими источниками и стоками, описанная в разделе 26.1 Существуют другие комбинаторные задачи, которые на первый взгляд имеют мало общего с транспортными сетями, однако могут быль сведены к задачам поиска максимального потока. В данном разделе рассматривается одна из подобных задач: поиск максимального паросочетания в двудольном графе (см.
раздел Б.4). Чтобы решить данную задачу, мы воспользуемся свойством полноты, обеспечиваемым методом Форда-Фалкерсона. Мы также покажем, что с помощью метода Форда-Фалкерсона можно за время О (У Е) решить задачу поиска максимального паросочетания в двудольном графе С = (У, Е). Глава 26. Задача о максимальном потоке Задача поиска максимального паросочетания в двудольном графе Пусп дан неориентированный граф С = (К Е). Паросочеюиинием (шаш1зшй) называется подмножество ребер М С Е, такое что для всех вершин е е У в М содержится не более одного ребра, инцидентного с.
Мы говорим, что вершина с е У является связанной (ша~след) паросочетанием М, если в М есть ребро, инцидентное э; в противном случае вершина о называется открытой (цпша1сЬед). Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочегание М, что для любого паросочетания М' (М) > ~М').
В данном разделе мы ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества У = Ь 0 гь, где Ь и В не пересекаются, и все ребра из Е проходят между Ь и В.
Далее мы предполагаем, что каждая вершина из 1' имеет по крайней мере одно инцидентное ребро. Иллюстрация понятия паросочетания показана на рис. 26.7. Задача поиска максимального паросочетания в двудольном графе имеет множество практических приложений. В качестве примера можно рассмотреть паросочетание множества машин Ь и множества задач гс, которые должны выполняться одновременно.
Наличие в Е ребра (и, с) означает, что машина и е Ь может выполнять задачу ю Е В. Максимальное паросочетание обеспечивает максимальную загрузку машин. б) б) Рис. 26.7. Двудольный граф С = Я Е) с разбиением вершин У = Ь 0 В. а) Паросочетание с мощностью 2. б) Максимальное паросочетание с мощностью 3. Часть Ч!. Алгоритмы для работы с графами 758 Поиск максимального наросочетания в двудольном графе С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентнрованном двудольном графе С = 1Ъ;Е) за время, полиномиально зависящее от Щ и 1Е). Проблема состоит в том, чтобы построить транспортную сеть, потоки в которой соответствуют паросочетаниям, как показано на рис.
26.8. Определим для заданного двудольного графа С соответствующую транспортную сеть С' = (Г, Е') следующим образом. Возьмем в качестве источника з и стока 1 новые вершины, не входящие в У, и пусть Ъ" = $' О (з, г). Если разбиение вершин в графе С задано как 1г = Ь о В, ориентированными ребрами С' будут ребра Е, направленные из Ь в тт, а также 1Ц новых ребер Е' = Цз,и): и Е Ь) 0 ((и,и): и Е Ь,и Е тт и (и,и) Е Е) О1(и,1): иветт). Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность. Поскольку каждая вершина из множества вершин Ъ" имеет по крайней мере одно инцидентное ребро, 1Е) > )Ъ")/2.
Таким образом, 1Е! < ~Е'~ = = (Е(+ (Ц < 3)Е), так что )Е'~ = 9 (Е). б) Рнс. 26.8. Двудольный граф (а) н соответствующая ему транспортная сеть (б). Выделенные ребра обеспечивают максимальный поток н определяют максимальное паросочетанне Следующая лемма показывает, что паросочетание в С непосредственно соответствует некоторому потоку в соответствующей транспортной сети С'. Поток г" в транспортной сети С = (К Е) называется нелочисленньии (1лтейег-ча)иед), если значения Г" (и, и) целые для всех (и, и) Е Ъ' х У. Лемма 26.10. Пусть С = 1'1г, Е) — двудольный граф с разбиением вершин У = = Ь 0 тт, и пусть С' = (Г, Е') — соответствующая ему транспортная сеть. Если 759 Глава 26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
