заметить, что начальный ноток минимальной стоимости всегда имеется, так как нулевой поток является потоком минимальной стоимости со значением 0.

Алгоритм, который мы собираемся описать, основан на вычислении кратчайшей цепи и следующей теореме.

Теорема 6. Если - поток минимальной стоимости в графе G со значением v и Р* - кратчайишя цепь {наименьшей стоимости) от S Kt в инкрементальном графе (), то % + I о (Р*) является потоком минимальной стоимости со значением v + I.

Доказательство теоремы очень просто - надо показать, что если G {%) не содержит никакого цикла отрицательной стоимости, то (I -Ь 1 ° {Р*)) также не содержит таких циклов. После этого все следует непосредственно из теоремы 5.

5.2.1. Описание алгоритма

Шаг 1. Начать с нулевых потоков на дугах и с потока, имеющего нулевое значение.

Шаг 2. Построить инкрементальный граф G{%) = {X, А^ U А^), как это описано в разд. 2.3, и взять следующие стоимости дуг:

для любой дуги (xf f)A-. положить Cij = Ci;, для любой дуги {xf, xf)A2 положить cfi - Cij.

Шаг 3. Найти в графе G () кратчайшую цепь Р* от вершины s к вершине t.

Шаг 4. Найти наибольшую величину б того потока, который можно послать вдоль Р* не изменяя структуру графа G (). Величина S равна

6= min [qf.].

{xf, xf) в p*

Шаг 5. (I) Если значение потока -Ь б о {Р*) меньше, чем требуемая величина v, произвести замену -f- б о {р*) и вернуться к шагу 2.

(II) Если значение потока -г б <= (Р*) равно v, остановиться. 14-6° (Р*) является требуемым потоком минимальной стоимости.

(III) Если значение потока -Ь б о {Р*) = й > у, остановиться. Требуемым потоком минимальной стоимости будет -\-+ (S + v){P*).

Здесь важно отметить, что граф G () на шаге 2 содержит как дуги положительной стоимости, так и отрицательной, и поэтому алгоритм кратчайшей цепи, используемый на шаге 3, не может быть алгоритмом Дейкстры, а должен быть (менее эффективным)

6, Потоки в графах с выигрышами

До сих пор в этой главе делалось предположение, что поток, выходящий из дуги, является таким же, как и поток, входящий в дугу. Однако в ряде практических ситуаций это допущение не выполняется. Например, в трубопроводе, по которому перекачивается жидкость, или в электрической сети могут быть потери, уменьшающие поток по дуге. В системах транспортировки может происходить порча груза, которая также приводит к уменьшению потока по дуге, представляющей маршрут. В технологических процессах, которые могут быть изображены графами с дугами, соответствующими операциям, ценность материала, покидающего дугу, больше, чем ценность материала, входящего в дугу, так как в дуге имеется выигрыш, получаемый за счет прибавочной стоимости операции. В задачах обмена (например, при продаже и покупке валюты) выигрыши дуг представляют обменный курс входного потока (измеряемый в одной валюте) по отношению к выходному потоку (измеряемому в другой валюте).

В этом разделе мы рассмотрим задачу нахонедения максимального потока (от S к f) в графе с произвольными неотрицательными выигрышами gij и пропускными способностями Qij, приписанными дугам (Xj, X]) графа G. Эта задача аналогична задаче о максимальном потоке (от S к t), обсунедавшейся в разд. 2, хотя теперь входной

алгоритмом, описанным в разд. 2.2.1 гл. 8. Однако Хаувер, Эд-мондс и Карп предложили недавно метод, позволяющий обойти вышеуказанную трудность и использовать более аффективные алгоритмы кратчайшей цепи.

5.2.2. Пример. Снова вычислим поток минимальной стоимости со значением 20 для графа, изображенного на рис. 11.13. Вначале берем 1 = 0. Инкрементальный граф изображен на рис. 11.13. Кратчайшей цепью в графе будет Р* = (жц х^, х^, Xg, х,) со значением 22, а б оказывается равным 12.

Поток I переходит в 12 о {Р*). Кратчайшей цепью в соответствующем инкрементальном графе будет P=,{a;i, х^, х^, х^, Xj) со стоимостью 23 и б равным 4.

Поток становится равным 12 о (Р*) + 4 о (Р*). Кратчайшей цепью в () будет Р* = (ж^, х^, х^, х^) со стоимостью 25 и 6 = 1.

Поток становится равным 12 о (Р*) + 4 о (Р*). Кратчайшей цепью в № (1) будет Р* = {ху, х^, х^, ж,) со стоимостью 31, и вдоль этой цепи можно послать 3 оставшиеся единицы потока для получения потока минимальной стоимости, изображенного на рис. 11.14 л.

То есть поток, порождаемый в самой вершине s.- Прим. ред. То есть поток, поглощаемый в самой вершине t.- Прим. ред.

и выходной потоки связаны между собой только через посредство графа G, способного как породить , так и поглотить поток.

Если через обозначить ноток, входящий в дугу (Xj, Xj), а через °j - ноток, выходящий из этой дуги, то

lb-=gijlb- (11.12)

Предположим далее, что пропускные способности дуг согласованы только с входными потоками, т. е. для любой дуги

1Ь<Яи (11.13)

независимо от величины Обозначим чистый входной ноток ) в S через Уз, а чистый выходной ноток ) в t через vt. Поток S = = (It 1°) является допустимым, если он удовлетворяет условию непрерывности потока во всех вершинах, т. е.

{Vs для Xi = S, -Vt для Xi==t, (11.14) о для XiS, t,

а также условиям (11.12) и (11.13) для каждой дуги (х^, Xj) из G. Введем теперь два определения.

Определение. Допустимый поток В = (°, °) называется максимальным, если он имеет наибольшее значение ut (скажем, у,) среди всех допустимых потоков.

Определение. Допустимый ноток S = (*, 1 ) называется оптимальным, если для любого другого допустимого потока S

или Vt vt, когда и^= Vs, или Vs Vst когда vt = vt,

где Vs и Vt являются соответственно чистыми потоками в источнике и стоке потока 3.

Эти последние условия согласуются с интуитивным пониманием оптимальности, а именно заданные v Vt являются или наибольши-&ш, или наименьшими возможными.

Определение. Допустимый поток S называется оптимально-максимальным, если он является как оптимальным, так и максимальным потоком.

Проиллюстрируем введенные понятия на примере. Рассмотрим граф на рис. 11.16 а, где первое число у дуги задает ее нро-нускную способность, а рторое - выигрыш. Тогда