Дискретно-непрерывная математика (стр. 93 )

φ1, φ2, φ3,..... имеющих величины 1, 2, 3,... В конечном счете мы получим поток φk, имеющий максимальную величину. Согласно теореме 5 это произойдет при k= , т. е. ког­да один или несколько разрезов {W, W′} будут насы­щены, это означает, что φk (a) =β(а) для каждой дуги a W→W′ и φk (а)=0 для каждой дуги aW′→W. Прежде чем описать алгоритм построения такой после­довательности допустимых потоков, видоизменим вве­денный ранее граф приращений. Будем считать, что каждой дуге а(v, w) в сети N в графе I(N, φ) соот­ветствуют две дуги а и a'(w, v). Припишем каждой дуге длину, пользуясь следующими соотношениями:

(Заметим, что вместо ∞ мы можем использовать неко­торое положительное число. Однако принятое условие позволит в дальнейшем с минимальными изменениями построить алгоритм минимизации стоимости. Таким об­разом, дуги, которые ранее удалялись из графа I(N, φ), теперь восстанавливаются, но имеют бесконечную длину, и поток φ будет максимальным, если между v1 и vn нет путей нулевой длины.)

Далее, через I будет обозначен граф приращении (структура которого не зависит от φ), а через λk — функ­ция расстояния, связанная с потоком φ k, имеющим вели­чину k.

Алгоритм определения максимального потока:

1. Положим і=0 и возьмем в качестве φ0 поток, тождественно равный нулю по каждой дуге.

2. Пользуясь функцией расстояния λi, определим кратчайшее расстояние между v1 и vn в I. (Это можно сделать, используя метод пометок )

3. Если расстояние, определенное на втором шаге, конечно, то обозначим через С любой простой путь из v1 в vn кратчайшей длины, и пусть σc обозначает соответствующий простой поток по цепи в сети N. Положим φi+1 = φi +σс и повторим шаг 2, заменяя i на i+1.

4. Если кратчайшее расстояние от v1 до vn равно ∞, то φ1 является максимальным потоком, и на этом алго­ритм работу заканчивает.

Такая процедура имеет один серьезный недостаток, а именно, величина потока увеличивается на каждом шаге только на единицу. На практике ее можно суще­ственно ускорить. Найдя путь С на шаге 3, можно про­верить, сколько единиц потока можно пропустить по этому пути. Другими словами, мы можем определить наибольшее целое t такое, при котором φi +tσс является допустимым потоком. Чтобы определить t, заметим, что для каждой дуги а(v, w) такой, что λ(а)<∞, к φi(а) можно добавить не более β(а)— φi(а) единиц потока, не нарушая допустимости. Аналогично, если λi(а′)<∞, из φi(а) можно исключить не более φi(а)—α(а) единиц потока.

Целое число t соответствует минимуму по таким при­ращениям потока в дугах С, и на шаге 3 алгоритма можно определять не φi+1 а

φi+1 = φi +σс.

Упражнение 8. Возьмите сеть рис. 6.8, для которой мы уже не формально получили максимальный поток. Решите задачу формально, пользуясь приведенным выше алгоритмом нахождения максимально­го потока.

6.8. Максимальные потоки в сетях общего вида с ограниченными пропускными способностями дуг

Если α(а)>0 для одной или более дуг и известен допустимый поток φi, имеющий величину i, то описанный алгоритм можно использовать для получения допусти­мых потоков с величинами, возрастающими от i до или убывающими от i до * (В этом случае шаг 2 надо видоизменить и находить кратчайшее расстояние от vn до v1 в текущем графе приращений.)

Однако, если первоначальный допустимый поток нe известен, то возникают трудности. Очевидно, что в этом случае (при α(а)>0) поток, тождественно равный нулю, не является допустимым.

Для нахождения начального допустимого потока сформулируем вспомогательную задачу на вспомога­тельной сети N'. Сеть N′= (V′, А') получается из сети N(V, А) следующим образом. Мно­жество вершин V′ состоит из вершин v1, ..., vn множе­ства V и двух добавочных вершин v0 и vn+1 (которые будут соответственно источником и стоком во вспомога­тельной сети).

Каждой дуге в множестве А' соответствуют три дуги

Этим дугам приписываются следующие пропускные спо­собности:

Заметим, что для дуг, у которых α(а)=0, построение дуг а" и а'" является излишним, так как для них α=β= 0. На практике эти дуги опускаются. В теории, од­нако, удобно считать, что все три дуги а', а" и а"' всегда существуют.

Кроме названных дуг в N′ добавляется еще одна конечная дуга b', имеющая следующие характеристики:

где К— целое число, большее чем величина любого воз­можного допустимого потока в первоначальной сети N. На рис. 6.10 приведен пример, иллюстрирующий вспо­могательную сеть N' для заданной сети N.

Рис. 6.10.

Замечание. Вспомогательная сеть полностью оп­ределяется сетью N и ее функциями ограничений α и β. Если N—сложная сеть, то явное построение N' оказы­вается в лучшем случае трудным делом. Однако для построения вспомогательной сети и реализации вычис­лительного алгоритма можно использовать электронные цифровые вычислительные машины.

Упражнение 9. На рис. 6.7 положите α=1 и β = 3 для каждой из вертикальных дуг и постройте вспомогательную сеть, принимая v1 в качестве источника и v5 в качестве стока. Укажите величины α' и β' для каждой дуги сети N'.

Вспомогательная сеть представляет интерес по двум причинам. Во-первых, N' — транспортная сеть, а для нее в предыдущем разделе дан алгоритм нахождения максимального потока. Во-вторых, можно показать, что максимальный поток φ' в сети N' можно легко преобра­зовать в допустимый поток φ в сети N, если допустимый поток в принципе существует. Отсутствие допустимого потока также легко устанавливается по характеристикам потока φ'.

Допустимый поток φ' из v0 в vn+1 в сети N' называет­ся насыщающим потоком, если φ'(а") =β'(а") для каж­дой дуги а", идущей из v0. Такой поток (если он суще­ствует) с необходимостью является максимальным в N' (почему?). Эквивалентным условием насыщающего потока является равенство φ'(а′")=β'(а'") для каждой дуги, оканчивающейся в vn+1. Если φ'—насыщающий поток в N′, то рассмотрим следующую функцию φ, опре­деленную на дугах сети N: φ (a) =φ'(а') +α(а). Для оп­ределенной таким образом φ доказывается следующая

Теорема 6.6. Если φ'—насыщающий поток в сети N' и φ определено так, как показано выше, то φ есть допустимый поток из v1 в vn сети N. Более того, вели­чина φ равна φ'(b').

Упражнение 10. Доказать теорему 6.6. Заметим, что должны быть обоснованы три факта:

Таким образом, если, максимизируя поток в сети N, мы получим насыщающий поток, то из него легко можно получить допустимый поток φ в сети N, С другой сто­роны, если максимальный поток в N' не является насы­щающим, то, как утверждается теоремой 7, допусти­мого потока в сети N не существует.

Теорема 6.7. Если φ'— максимальный, но не насы­щенный поток в сети N' из v0 в vn+1, то в сети N не су­ществует допустимого потока из v1 в vn.

Доказательство. Обозначим через W множество вершин, отличных от v0, но достижимых из v0 путями конечной длины в графе I(N', φ'). И пусть W′ обозна­чает вершины, не достижимые из v0 и отличные от vn+1. Так как φ ' — ненасыщающий поток, оба множества W и W′ непусты. Пропускная способность (т. е. сумма верхних границ потока) разреза → ′, определенного разбиением V′ на ={ v0) W и