6.1. Аугментальные маршруты

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

А. Выигрыш маршрута.

Выигрыш маршрута определяется так:

Б. Пропускная способность маршрута.

Инкременталъная пропускная способность аугментального маршрута равна значению такого максимального входного потока в вершине который может быть послан по данному маршруту к вершине и либо насыщает поток в некоторой прямой дуге из либо обращает в нуль поток в некоторой обратной дуге маршрута

Если цепь и в входит поток величины то входной лоток (в вершине на дуге из равен

где множества соответственно прямых и обратных дуг подцепи выигрыш цепи

(кликните для просмотра скана)

Если прямая дуга из несущая поток то эта дуга будет насыщена, если Если же поток несет обратная дуга, то ее поток станет равным нулю, когда т. е. когда Инкрементальная пропускная способность цепи дается выражением

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

Для цепи на рис. 11.17 (а) и заданного начального потока добавление потока в вершине приводит к потоку, изображенному на рис. Максимальное значение оставляющее поток допустимым, равно тогда Для этого значения поток по дуге сводится к нулю, т. е. перестает быть аугментальной цепью в новом графе Если бы начальный поток, входящий в дугу был равен, скажем, 8 вместо 2, то максимальное допустимое значение было бы тогда 2,1 — значение, при котором дуга из была бы насыщена.

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