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

Построение потоков, имеющих заданную величину, с помощью добавления к некоторому начальному до­пустимому потоку или исключения из него простых потоков по цепям является не только теоретическим приемом, но и практическим методом. Перед тем как дать точное описание этого процесса, проиллюстрируем его основные особенности неформально, используя в ка­честве примера транспортную сеть, изображенную на рис. 6.8. Числа на рис. 6.8, а показывают пропускные способности дуг, a v и w — источник и сток соответствен­но.

Рис. 6.8.

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

Наша цель — максимизировать поток из v в w. Оче­видно, что максимальная величина не может быть больше 5 из-за пропускных способностей дуг, инцидент­ных вершине v. В начале возьмем любой путь, соеди­няющий v с w, например, путь, определенный следующей последовательностью вершин v, у, х, w, и припишем каждой дуге пути поток величины 2. (Любая большая величина будет выше пропускной способности некоторых дуг.) Дугам, не входящим в рассматриваемый путь, пер­воначально припишем потоки, равные нулю. Полученный в результате поток показан на рис. 6.8, b.

Найдем теперь любой другой путь, который не ис­пользует насыщенных дуг (т. е. дуг, подобных дугам (v, у) и (х, w), для которых проходящий через них поток уже равен пропускной способности). Возьмем, например, путь, определенный последовательностью вер­шин v, х, z, w, и припишем единичный поток каждой из его дуг. Добавив полученный поток к предыдущему потоку рис. 6.8, b, получим новый поток рис. 6.8, с. В последнем случае три дуги насыщены (они помечены крестиками). Так как мы должны избегать насыщенных дуг, то единственный способ, с помощью которого можно увеличить величину потока из v в w, состоит в том, чтобы отказаться от ранее принятого решения пропус­тить поток от у к х. Добавим поток величины 2 в цепь, определяемую последовательностью вершин v, x, у, z, w. Полученный в результате поток показан на рис. 6.8, d. Таким образом, в результате исключения потока из ребра, соединяющего вершины х и у, получен поток, величина которого, очевидно, максимальна.

Вернемся теперь к формальному описанию синтеза потоков с помощью потоков по цепям. Эта процедура наиболее легко описывается с помощью вспомогательно­го ориентированного графа, так называемого графа при­ращений. Если φ — допустимый поток в сети N(V, А), то соответствующий граф, приращений І(N, φ) есть ориен­тированный граф, имеющий те же самые вершины, что и сеть N. Дуги этого грифа определяются следующим образом: для каждой дуги

a (v, w) из N в графе І(N, φ) строится дуга а, если φ(a)<β(a), а дуга а' с обращен­ной ориентацией a'(v, w), если φ(a)<α(a). Если в графе

I(N, φ) есть дуга а или а', то можно добавить или соответственно вычесть единицу потока в а, не на­рушая допустимости потока по этой дуге. На рис. 6.9 (справа) показан граф приращений, соответствующий сети.

Рис. 6 9.

Допустимый поток изображен на рис. 6.9 слева.

(Тройка чисел у дуг обозначает α(а), φ (а) и β(а) соответственно.)

Каждый простой путь из v1 в vn в графе I(N, φ) определяет простой поток по цепи из v1 в vn в сети N; его можно добавить к φ, не нарушая условия допустимости. На рис. 6.9 (справа) путь {а1, а3, а5} в I(N, φ) опреде­ляет простой поток по цепи σ в сети N, где а1 и а5 — нормальные дуги, а а3 — обращенная дуга. Аналогично, каждый простой путь из vn в v1 в графе I(N, φ) опреде­ляет простой поток по цепи σ* из v1 в vn такой, что φ — φ* является допустимым в N. Наличие пути { а′4, а′1} указывает на то, что поток по цепи, проходящий через нормальные пути а1 и а4, можно вычесть из φ без нару­шения условий допустимости.

Очевидно, что если φ — допустимый поток, имеющий максимальную величину, то в I(N, φ) не существует путей из v1 в vn. Аналогично, если φ — допустимый по­ток, имеющий минимальную величину, то в I(N, φ) не существует путей из vn в v1 за исключением случая, когда φ равен нулю. (Напомним, что согласно нашему определению, величина потока должна быть неотрица­тельной. Если I(N, φ) содержит путь из vn в v1 и вели­чина φ равна нулю, то φ—σ будет допустимым для соот­ветствующего потока по цепи σ, но не для потока из v1 в vn.

Мы видели ранее, что необходимым условием суще­ствования допустимого потока является выполнение не­равенства ≤. Обозначим * = max {, 0} для иск­лючения потоков, имеющих отрицательные величины. Тогда теорема 5 утверждает, что * и дают точные границы величин допустимых потоков, если такие потоки существуют.

Теорема 6.5. Если существует хотя бы один допусти­мый поток из v1 в vn, то * и — соответственно мини­мальная и максимальная границы величин допустимые потоков.

Доказательство. Пусть φ — допустимый поток из v1 в vn такой, что I(N, φ) не содержит путей из v1 в vn. (Такой поток всегда можно построить, начиная с любого допустимого потока и добавляя последователь­ность простых потоков по цепям до тех пор, пока в графе I(N, φ) не окажется путей из v1 в vn.) Пусть W состоит из v1 и всех вершин, которые достигаются из v1 с по­мощью пути. Тогда vn W по предположению. Более того, для каждой дуги в W′→ W мы должны иметь φ (а)=β(а), а для каждой дуги в W′→ W φ(а)=α(а) (почему?). Но мы знаем, что величина φ, равная, напри­мер, k, определяется выражением

Так как

для каждого разбиения {W, W′}, данное значение W должно реализовать и величина потока φ равна . Аналогично обосновывается вторая часть теоремы. В этом случае, начиная с любого допустимого потока, мы можем последовательно вычитать потоки по цепям до тех пор, пока не получим поток нулевой величины, или не исключим все пути из vn в v1 в графе I(N, φ). В первом случае *=0, существует поток нулевой ве­личины и доказательство закончено. В последнем случае, пусть W есть множество вершин, не достижимых из vn с помощью путей в графе I(N, φ). Тогда φ(а)=α(а) для дуг множества W→W′ и φ(а)= β(а) для дуг мно­жества W′→ W и величина k потока φ удовлетворяет соотношению

Таким образом, допустимый поток величиной * суще­ствует. Теорема доказана.

При α(а)=0 для каждой дуги допустимый поток обязательно существует и теорема 6.5 в этом случае называется теоремой о максимальном потоке и мини­мальном разрезе.

6.7. Максимальный поток в транспортной сети

В транспортной сети всегда существует допустимый начальный поток, а именно поток, тождественно равный нулю. Обозначим этот поток через φ0. Воспользуемся процедурой увеличения потока из доказательства теоремы 6.5 и найдем последовательность потоков