Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 169
Текст из файла (страница 169)
Цикл иййе будет выполняться эффективно, если реализовать транспортную сеть С = (К Е) с помол(ью правильно выбранной структуры данных и искать увеличивающий путь с помощью алгоритма с линейным временем работы. Предположим, что мы поддерживаем структуру данных, соответствующую ориентированному графу С' = (К Е'), где Е' = ((и, и): (и, и) е Е или (п, и) е Е). Ребра ~Мели Форла-Фалкнкона может работась бесконечно, только если зналелнв пропускной способностл ребер лвллмтсл нерациональными ласками 7бб Часть Гй Алгоритмы для работы с уафама ,чч гя: яа ччч сдс '~-.: . ась:, ччл. ю (в) Рис. 20.7. (в) Транспортная сеть, для обработки которой алгоритму Гоко-Гьькккзон мткег потребоваться время В(Е )У и, где 7 предсгввляег собой максимальный поток, который в линном случае имеет величину ~У") = 2000000.
Шгриковкой выделен увеличивяющий пугь с оствгочной пропускной способностью 1. (б) Полученная остягочивл сеть с другим увеличивающим пуюм с остаточной пропускной способностью 1, (в) Полученная в результате осгягочнвя сеть. сети С являются также ребрами графа С', поэтому в тмюй структуре данных можно довольно лепа хранить пропускные способности и потоки. Для данного потока Х в С ребра остаточной сети Су состоят из всех ребер (и, о) графа С', таких, что су(и, и) > О, где су удовлетворяет уравнению (26.2). Следовательно, время поиска пути в остаточной сети составляет 0((7+ Е') = 0(Е), если используется либо поиск в глубину, либо поиск в ширину.
Таким образом, каждая итерация цикла чг)гйе занимает время О(Е), что вместе с инициализацией в строках 1 н 2 делает общее время выполнения алгоритма ГОКО-ГП.КЕКЗ(ПЧ равным 0(Е ~Х'~). Когда значения пропускньгх способностей являются целыми числами и оптимальное значение потока ~~'~ невелико, время выполнения алгоритма Форда— Фапкерсона достаточно неплохое.
Но на рис. 26.7,(а) показан пример того, что может произойти в простой транспортной сети с большйм значением ~~'~. Величина максимального потока в данной сети равна 2 000 000: 1000000 единиц потока идет по пути л -+ и — > (, а другие 1 000 000 единиц идут по пути и — з и -+ (. Если первым увеличивающим путем, найденным процедурой Гокп-Г()ькйкзо)ч, является путь и -+ и -ь е — + (, как показано на рнс. 26.7,(а), поток после первой итерации имеет значение 1. Полученная остаточная сеть показана на рис. 26.7, (б). Если в ходе выполнения второй итерации будет найден увеличивающий путь л -+ и -+ и -+ (, как показано на рис 26 7, (б), поток станет равным 2. На рис.
26 7, (в) показана соответствующая остаточная сеп . Можно продолжать процедуру, выбирая увеличивающий путь л -+ и -+ о -+ ( в нечетных итерациях и л — к и -ь и -+ ( в четных. В таком случае нам придется выполнить 2000000 увеличений, при этом величина потока на каждом шаге увеличивается всего на 1. Алгоритм Эдмондов-Карпа Можно улучшить временную границу алгоритма Гокп-Г(л.кйкзо)ч, если реализовать вычисление увеличивающего пути р в строке 3 как поиск в ширину, т.е. если в качестве увеличивающего пути выбрать краглчайший путь из л в ( в остаточной сети, где каждое ребро имеет единичную длину (вес). Такая реализация метода Форда-Фалкерсона называется гьзгоривгмаы Эдмомг)са-Карла Глава ЗД Задача о максимальном автоле 7б7 (Ебзпопдз-Клгр а!копани).
Докажем, что время выполнения алгоритма Эдмондса— Карпа составляет 0(17Ез). Анализ зависит от расстояний между вершинами остаточной сети СГ. В следующей лемме длина кратчайшего пути из вершины и в и в остаточной сети Се, где каждое ребро имеет единичную длину, обозначена как бе(и, и). Лемма 26. 7 Если применить алгоритм Эдмондса-Карпа к транспортной сети С = ($е, Е) с ис- током з н стоком г, то дпя всех вершин и е 17 — (в,1) длина кратчайшего пу- ти бу(в, и) в остаточной сети СГ монотонно увеличивается с каждым увеличени- ем потока.
бе (в,и) = бу (в,и) — 1 (26.12) Исходя из того, как мы выбирали и, можно утверждать, что длина пути до вер- шины и из истока в не уменьшилась, т.е. бГ (з, и) > 67(в, и) . (26.13) Мы утверждаем, что (и, и) ф ЕГ. Почему? Если мы имели (и, и) е Еу, то должны были также выполняться соотношения бу(в,и) < бу(в,и) +1 < б7 (в, и) + 1 = б7 (в, и) (лемма 24.10, неравенство треугольника) (согласно неравенству (26.13)) (согласно уравнению (26.12)), что противоречит нашему предположению о том, что б7 (з, и) < бу(в, и).
Как же может получиться (и, и) ф ЕГ и (и,и) Е ЕГ? Увеличение должно привести к возрастанию потока из и в и. Алгоритм Эдмондса — Карпа всегда увеличивает поток вдоль кратчайших путей, поэтому последним ребром кратчайшего пути из в в и в СЗ является ребро (и, и). Следовательно, бу(з,и) = бу(в,и) — 1 < бр(з,и) — 1 = бе (в,и) — 2 (согласно неравенству (26.13)) (согласно уравнению (26.12)), Доказашельсшво.
Предположим, что для некоторой вершины и Е Ъ' — (з,1) сушествует такое увеличение потока, которое приводит к уменьшению длины кратчайшего пути из в в и, и покажем, что зто предположение приведет нас к противоречию. Пусть З вЂ” поток, который был непосредственно перед первым увеличением, приведшим к уменьшению длины некоего кратчайшего пути, а 7'— поток сразу после этого увеличения. Пусть и — вершина с минимальной длиной кратчайшего пути бу (в, и), которая уменьшилась в результате увеличения потока, так что бу (в, и) < бе(з, и).
Пусть р = в - и + и — кратчайший путь из в в и в СГ, такой, что (и, и) Е Ее и 7бз Части П. Алгоритиы зла работы с графами что противоречит нашему предположению о том, что бу(з,и) < бг(з,и). Мы заключаем, что наше предположение о существовании такой вершины и неверное.
В следующей теореме устанавливается верхний предел количества итераций алгоритма Эдмондса-Карпа. Теорема 26.8 Если алгоритм Эдмондса — Карпа выполняется для некоторой транспортной сети С = (1г, Е) с истоком з и стоком г, то общее число увеличений потока, выполняемых данным алгоритмом, составляет 0(КЕ). Доказательство. Назовем ребро (и,и) остаточной сети Су критическим (спйса1) для увеличивающего пути р, если остаточная пропускная способность р равна остаточной пропускной способности ребра (и, и), те.
если сг(р) = сг(и, и). После увеличения потока вдоль увеличивающего пути все критические ребра этого пути исчезают из остаточной сети. Кроме того, по крайней мере одно ребро любого увеличивающего пути должно быть критическим. Теперь покажем, что каждое из 1Е! ребер может становиться критическим не более Щ /2 раз. Пусть и и и являются вершинами из множества вершин К, соединенными некоторым ребром из множества Е.
Поскольку увеличивающие пути являются кратчайшими путями, то, когда ребро (и, и) становится критическим в первый раз, справедливо равенство бг(з, и) = бу(з, и) + 1 . После того как поток увеличен, ребро (и, и) исчезает из остаточной сети. Оно не может появиться в другом увеличивающем пути, пока не будет уменьшен поток из и в и, а это может произойти только в том случае, если на некотором увеличивающем пути встретится ребро (и, и). Если в этот момент в сети С поток представляет собой г"', то справедливо следующее равенство бу (з,и) = бу (з,и) + 1. Поскольку бу(з, и) < бу (з, и), согласно лемме 26.7, мы имеем бр(з, и) = бр(з, и) + 1 > бу(з, и) + 1 = бу(з, и) + 2 .
Следовательно, за время, прошедшее с момента, когда ребро (и, и) стало критическим, до момента, когда оно станет критическим в следующий раз, расстояние до и от истока увеличивается не менее чем на 2. Расстояние до и от истока в начальный момент было не меньше О. Среди промежуточных вершин на кратчайшем пути из з в и не могут находиться з, и илн г (поскольку наличие ребра (и, и) в увеличивающем пути влечет за собой и ф 8). Следовательно, к тому Глава 26 Эадало о максимальном лотокв 7б9 моменту, когда вершина и станет недостижимой из истока (если такое произойдет), расстояние до нее будет не более ٠— 2. Таким образом, ребро (и, о) может стать критическим не более чем еще (٠— 2)/2 = (Ц /2 — 1 раз, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
