Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 155
Текст из файла (страница 155)
Полученная остаточная сеть показана на рис. 26.66. Если в ходе выполнения второй итерации найден увеличивающий путь з — о -+ и -> т, как показано на рис. 26. 66, поток станет равным 2. На рис. 26.6в показана соответствующая остаточная сеть. Можно продолжать процедуру, выбирая увеличивающий пуп з и — + ц — 8 для итераций с нечетным номером а -~ и и г для итераций с четным номером. В таком случае нам придется выполнить 2000000 увеличений, при этом величина потока на каждом шаге увеличивается всего на 1 единицу. Алгоритм Эдмоидса-Карпа Указанный недостаток метода Форда-Фалкерсона можно преодолеть, если реализовать вычисление увеличивающего пути р в строке 4 как поиск в ширину, т.е.
если в качестве увеличивающего пути выбирается кратчаймшй путь из з Глава 26. Задача о максимальном потоке 753 в ~ в остаточной сети, где каждое ребро имеет единичную длину (вес). Такая реализация метода Форда-Фалкерсона называется алгоритмом Эдмондса-Карпа (ЫшоиЬ-Кагр а18опйип). Докажем, что время выполнения алгоритма ЭдмондсаКарпа составляет О (г' Ез).
Анализ зависит от расстояний между вершинами остаточной сети Су. В следующей лемме длина кратчайшего пути из вершины и в и в остаточной сети Су, где каждое ребро имеет единичную длину, обозначена как бу (и, и). Лемма 26.8. Если для некоторой транспортной сети С = (У, Е) с источником з и стоком т выполняется алгоритм Эдмондса-Карпа, то для всех вершин и е е Ъ' — (з, 1) длина кратчайшего пути бу (з, и) в остаточной сети Су монотонно возрастает с каждым увеличением потока. б~(з,и) = б'~(з,и) — 1. (26.7) Исходя из того, как мы выбирали и, можно утверждать, что длина пути до вер- шины и не уменьшилась, т.е.
б~У(з,и) > бу(з,и). (26.8) Мы утверждаем, что в таком случае (и, и) ф Е~. Почему7 Если (и, и) Е Е~, тогда справедливо следующее: бу (з,и) < бу (з,и)+ 1 < < бу~ (з, и) + 1 = = б~~(з,и) (согласно лемме 24.10, неравенство треугольника) (согласно неравенству (26.8)) (согласно уравнению (26.7)), что противоречит предположению б'~ (з, и) < бу (з, и).
Теперь посмотрим, как может получиться, что (и, и) ф Ег, но (и, и) Е Е~? Увеличение должно привести к возрастанию потока из и в и. Алгоритм ЭдмондсаКарпа всегда увеличивает поток вдоль кратчайших путей, поэтому последним Доказательство. Предположим, что для неюторой вершины и Е 'г' - (з, г) существует такое увеличение потока, юторое приводит к уменьшению длины кратчайшего пути из з в и, и покажем, что это предположение приведет нас к противоречию. Пусть г" — поток, который был непосредственно перед первым увеличением, приведшим к уменьшению длины некого кратчайшего пути, а Г"' — поток сразу после этого увеличения.
Пусть и — вершина с минимальной длиной кратчайшего пути б~ (з, и), которая уменьшилась в результате увеличения потока, т.е. б~ (з, и) < < бу (з, и). Пусть р = з -+ и — и — кратчайший путь от з к и в С~~, таюй что (и, и) Е Е~ и Часть Ч1 Алгоритмы для работы с графами 754 ребром кратчайшего пути из з в и в Су является ребро (и, и). Следовательно, бу(в,и) = бу (з,и) — 1 < < б~ (в,и) — 1 = = б~(в,и) — 2 (согласно неравенству (26.8)) (согласно уравнению (26.7)), что противоречит предположению б~~ (з, и) < бу (з, и), а значит, наше предположение о существовании вершины и не верно.
ы Следующая теорема устанавливает верхний предел количества итераций алгоритма Эдмондов-Карпа. Теорема 26.9. Если для некоторой транспортной сети С = (У, Е) с источником з и стоком 1 выполняется алгоритм Эдмондов-Карпа, то общее число увеличений потока, выполняемое данным алгоритмам, составляет О (У Е). бг (з, и) = бу (в, и) + 1. После того как поток увеличен, ребро (и, и) исчезает из остаточной сети. Оно не может появиться в другом увеличивающем пути, пока не будет уменьшен поток из и в и, а это может произойти только в том случае, если на некотором увеличивающем пути встретится ребро (и, и). Если в этот момент поток в сети С составлял Г"', справедливо следующее равенство: б~~(в,и) = б'~ (з,и) + 1.
Поскольку, согласно лемме 26.8, бу (в, и) < б' (в, и), получаем: б~ (з,и) = б~у (з, и) + 1 > бу (з, и) + 1 = бу (з,и) + 2. Следовательно, за время, прошедшее с момента, когда ребро (и, и) было критическим, до момента, когда оно становится критическим в следующий раз, расстояние до и от источника увеличивается не менее чем на 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з. Покажите, как преобразовать данную задачу поиска потока г", удовлетворяющего указанным дополнительным ограничениям, в задачу поиска максимального потока в транспортной сети с одним источником и одним стоком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
