Глава 11 ПОТОКИ в СЕТЯХ

1. Введение

Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой конечной вершине t (стоку). При этом каждой дуге (Xi, xj) графа G приписана некоторая пропускная способность д^, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача и ее варианты могут возникать во многих практических приложениях, например при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. В этом примере решение задачи о максимальном потоке укажет также ту часть сети дорог, которая насыщена и образует узкое место в отношении потока между двумя указанными концевыми пунктами.

Метод решения задачи о максимальном потоке (от s к t) был предложен Фордом и Фалкерсоном [12], и их техника пометок составляет основу других алгоритмов решения многочисленных задач, являющихся простыми обобщениями или расширениями указанной задачи. Следующие возможные варианты задачи о максимальном потоке (от s к t) встречаются в литературе.

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

(II) Рассмотрим случай, когда ищутся максимальные потоки между каждой парой вершин. Хотя такая задача может быть решена как п {п - 1)/2 отдельных (от sk t) задач, но это очень трудоемкий процесс. При нахождении кратчайших цепей между каждой парой вершин графа было установлено, что нет необходимости решать каждую (от s к t) задачу о кратчайшей цепи индивидуально

2. Основная задача о максимальном потоке (от s к t)

Рассмотрим граф G = {X, А) с пропускными способностями дуг qij, источником s и стоком f; s, t в X. Множество чисел 1;;, определенных на дугах {xt, Xj) 6.4, называют потоками в дугах.

(см. ГЛ. 8), и в настоящей задаче точно так же существует метод, который - для неориентированных графов - не предполагает обязательного решения задач о максимальных потоках для каждой пары вершин s ш f.

(III) Если вместо одного источника и одного стока рассмотреть несколько заданных источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то задача максимизации суммы всех потоков между источниками и стоками называется задачей о многопродуктовом потоке. В этой задаче пропускная способность qj дуги (а; xj) является ограничением для суммы всех потоков всех видов продуктов через эту дугу.

(IV) Во всех рассмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если отказаться от этого допущения и рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке (от S к f) называют задачей о потоках с выигрыишми. В такой задаче потоки могут и порождаться , и поглощаться самим графом, так что поток, входящий в s, и поток, покидающий t, могут изменяться совершенно независимо.

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

В этой главе мы обсудим основную задачу о максимальном потоке (от 5 к f) и ее обобщения (I), (III) и (IV). Так как алгоритмы для многопродуктового потока имеют совсем другую природу и совсем не так эффективны, как метод пометок, обсуждаемый в этой главе, то мы не будем заниматься здесь этой задачей и отсылаем заинтересованного читателя к [18, 27, 26, 25, 24, 15].

1) Если могут возникнуть неясности, то мы будем употреблять запим i (ij, Xj), q (i;, Xj), T (ij, Xj) и (ij, Xj) вместо сокращенных обозначение

Si; > 9гл и cij соответственно.

2) Или пропускной способностью.- Прим. ред.

если выполняются следующие условия:

iv, если Xi = s, - V, если Xi = t, (11.1)

О, если Х1ф8,г,

и

hjQtj для всех {Xi,Xj)A. (11.2)

Уравнение (11.1) является уравнением сохранения потока. Оно утверждает, что поток, втекающий в вершину, равен потоку, вытекающему из вершины, за исключением вершин, являющихся источником и стоком (вершин s и t), для которых существуют сетевые вытекания и приток величины v соответственно. Соотношения (11.2) указывают просто на то, что пропускные способности ограничены для каждой дуги графа G. Задача состоит в нахождении такого множества потоков по дугам, чтобы величина

v= И l.j= S hi (11.3)

XjETU) зсег-ч<)

была максимальной. Здесь и ht записаны для потоков из вершины S в Xj ш шз Xh в t соответственно.

Алгоритм расстановки пометок, предложенный Фордом и Фалкерсоном [12] для решения этой задачи, основан на следующей теореме (определение понятия разреза см. в гл. 9).

Теорема 1. (Теорема о максимальном потоке и минимальном разрезе [8, 10, 11].) Величина максимального потока иа s в t равна величине минимального разреза (Х^ Хт), отделяющего s от t.

Разрез Хд-Хо отделяет s от t, если s Хд и f Хд. Величиной 2) такого разреза называется сумма пропускных способностей всех дуг uaG, начальные вершины которых лежат в Х^, а конечные в Хд, т.е.

V(XgXg)= S qJ.

Минимальный разрез {Х^ Х^) - это разрез с наименьшим таким значением.

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