g (5) = min Г min {VitL-},

P P+l

min [Ь±йЬ\Л^ (11.17)

Если маршрут S не является цепью и, следовательно, некоторые дуги встречаются более чем один раз, то и в этом случае легко получить выражение, аналогичное (11.17).

Для цепи S на рис. 11.17 (а) и заданного начального потока добавление потока б в вершине х^ приводит к потоку, изображенному на рис. 11.17 (б). Максимальное значение б, оставляющее поток допустимым, равно тогда q {S) = 0,6. Для этого значения поток по дуге (х^, Ха) сводится к нулю, т. е. S перестает быть аугментальной цепью в новом графе G (В). Если бы начальный поток, входящий в дугу (4, Xs), был равен, скажем, 8 вместо 2, то максимальное допустимое значение б было бы тогда 2,1 - значение, при котором дуга {х^, хз) из S была бы насыщена.

Для маршрута S, изображенного на рис. 11.17 (в) и заданного начального потока добавление потока б в вершине даст ноток, показанный на рис. 11.17 (г). Инкрементальная пропускная способность этого маршрута равна 0,5 - значение, при котором дуга (хз, Х4) становится насыщенной.

6.2. Активные циклы

Так как цикл ) можно рассматривать как маршрут с совпадающими начальной и конечной вершинами, то выигрыш цикла и его пропускная способность могут быть определены так же, как и для маршрута. Цикл Ф называется активным в графе G (3) по отношению к вершине t, если

(I) его выигрыш больше единицы,

(II) его инкрементальная пропускная способность отлична от нуля,

(III) на Ф имеется некоторая вершина х;, для которой существует аугментальный маршрут от Xj к t.

1) Точнее - замкнутый маршрут.- Прим, ред.

Если {хг , Xi ) - прямая дуга из S, несущая поток f ,

р р р+1

то эта дуга будет насыщена, если Й . + б. , = Я< >

р'р+1 р*р+1 р р+1

Если же поток К , несет обратная дуга, то ее поток станет р+1 р

равным нулю, когда б = Й , , т. е. когда 6, , ==

р р+1 р+1 р PVP+1

~ gi . Й i . Инкрементальная пропускная способность

р+1 р р+1 р цепи S дается выражением

6.3. Алгоритм оптимального потока для графов с выигрышами

Из трех вышеприведенных теорем сразу же вытекает алгоритм оптимальности, описанный ниже.

Шаг 1. Начать с произвольного допустимого потока 3 в G (допустим, например, нулевой по каждой дуге поток).

Шаг 2. Найти в G (S) активный цикл Ф по отношению к t.

Шаг 3. Пусть Xj - такая вершина в Ф, что аугментальный маршрут начинается в Xj и кончается в t. (Заметим, что Xj может совпадать с t.) Начиная с вершины Xj, устроить циркуляцию потока б по активному циклу и передать избыток потока из Xj в f по аугмептальному маршруту. Выбрать б так, чтобы (вместе с существующим потоком В) инкрементальная пропускная способность цикла или аугментальпого маршрута уменьшилась до нуля.

Активный по отношению к начальной вершине s цикл может быть определен аналогично. Из вышеприведенного определения ясно, что с помощью циркуляции потока по активному циклу можно создать дополнительный поток (по свойству (I)) и передать его в вершину t (по свойству (III)). В вышеприведенном примере на рис. 11.16(b) поток порождался циркуляцией по активному циклу (х4, Ха, Хз, Х4).

Активный по отношенпю к t цикл называется дезактивированным, если добавление дополнительного потока в G осуществлено так, что или инкрементальная пропускная способность цикла уменьшилась до нуля, или пропускные способности всех аугментальных цепей от какой-либо вершины на цикле до вершины t уменьшились до нуля (т. е. в новом графе G (В) не может быть сделано больше никакого добавления ненулевого дополнительного потока). В [13] и [22] доказаны следующие утверждения.

Теорема 7. Поток В является оптимальным тогда и только тогда, когда граф G (S) не содержит никаких активных циклов по отношению к s или t.

Теорема 8. Пусть S является оптимальным потоком. Тогда если поток увеличить по какой-либо {от s к t) аугментальной цепи с наивысшим выигрышем, то вновь полученный поток также будет оптимал ьным.

Теорема 9. Поток В будет оптимально-максимальным, если некоторый разрез (Xq -> X - Xq), отделяющий s от t, является насыщенным и если не существует никакого активного цикла по отношению к t, все вершины которого лежат в X - Xq.

Шаг 4. Обновить поток В и возвращаться к шагу 2 до тех пор, пока все активные циклы не будут дезактивированы и больше не будет существовать никаких активных циклов; после чего перейти к шагу 5. (На этом этапе поток В будет оптимальным потоком В с у, = 0.)

Шаг 5. Найти аугментальный маршрут от s к f с наибольшим выигрышем. Посылать поток по этому маршруту до тех пор, пока инкрементальная пропускная способность не уменьшится до нуля.

Шаг 6. Обновить поток В и повторять шаг 5 до тех пор, пока или чистый выходной поток V не примет требуемое значение (оптимального потока), или больше не будет существовать никаких аугментальных маршрутов; тогда полученный поток будет оптимально-максимальным потоком В.

Шаги вышеприведенного алгоритма очень просты, а сам метод эффективен. Шаги 2 и 5 можно выполнять и с помощью алгдритма кратчайшей цепи. А именно определим инкрементальный граф

(S), соответствующий графу G (В), с множеством вершин = = Z и множеством дуг А^, таким, что

arf, xl е А^, если 0<fj<[gi., причем инкрементальная стоимость

с15= - log (gi) и пропускная способность

и

(xxr)e!Л^ если 0;<jtj<gij, инкрементальная стоимость

n=-log(i/go)

и пропускная способность

Цикл Ф в графе G (В), имеющий выигрыш, больший чем единица, соответствует тогда циклу с отрицательной стоимостью в графе G (В). В этом можно убедиться, прологарифмировав обе части соотношения (11.15), в котором в качестве маршрута S надо взять цикл Ф. Тогда получим

1ое[(Ф)]= 2 log(gг^)- 2 log(l/g;i) (xj,*.)eF (зс хрев

f в