О МАКСИМАЛЬНОМ ПОТОКЕ ЧЕРЕЗ СЕТЬ

Рассмотрим некоторую двухполюсную сеть, например изображенную на рис. 1. Ребра такой сети могут представлять каналы связи или вообще любые проводящие системы ограниченной пропускной способности, как, например, железнодорожные магистрали, системы энергоснабжения или трубопроводы, при условии, что в каждом случае возможно установить определенную максимально допустимую величину потока через данное ребро — пропускную способность ребра.

Рис. 1.

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

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

Ответ можно получить в терминах сечений сети. Сечение двухполюсной сети есть совокупность ребер, при удалении которых сеть распадается на две или большее число несвязанных частей с двумя полюсами в разных частях. Таким образом, каждый путь от одного полюса к другому в исходной сети проходит хотя бы через одно ребро сечения. В приведенной выше сети примерами сечений являются Под простым сечением будем подразумевать такое сечение, что если удалить любое его ребро, то оно перестанет быть сечением. Так являются простыми сечениями, в то время как не является таковым. Если в связной двухполюсной сети удаляется простое сечение, то сеть распадается ровно на две части: левую часть, содержащую левый полюс, и правую часть, содержащую правый полюс. Каждому простому сечению припишем значение, равное сумме пропускных способностей ребер этого сечения, причем пропускная способность ориентированного ребра учитывается только тогда, когда оно направлено из левой части сети в правую часть. Заметим, что направление ориентированного ребра нельзя, вообще говоря, вывести по его положению в графе, соответствующем сети. Ребро направлено слева направо в простом сечении тогда и только тогда, когда стрелка на этом ребре направлена из вершины левой части сети к вершине правой части. Так, в нашем примере сечение имеет значение а сечение имеет значение

Теорема. Максимальный поток слева направо через сеть равен минимальному значению всех простых сечений.

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

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

Для того чтобы доказать сначала, что поток через сеть не может превышать значения минимального сечения, рассмотрим произвольный заданный поток и сечение С с минимальным значением. Образуем алгебраическую сумму 5 потоков слева направо через это сечение. Ясно, что она меньше или равна значению V этого сечения, так как последнее получилось бы, если бы все пути слева направо в С были загружены вплоть до пропускной способности, а пути в обратном направлении не использовались. Прибавим теперь к 5 алгебраическую сумму потоков во всех вершинах правой относительно сечения С части сети. Эта сумма равна нулю ввиду того, что закон Кирхгофа соблюдается в каждой вершине. С другой стороны, видно, что эта сумма уничтожает каждый поток, представленный в сумме а также, что каждый поток по ребру, оба конца которого лежат в правой части, встречается как со знаком плюс, так и со знаком минус и, следовательно, уничтожается. Единственная остающаяся величина, которая не уничтожается, есть поток из правого полюса сети или, как говорят, суммарный поток через сеть. Заключаем отсюда, что

Докажем теперь более интересное положительное утверждение этой теоремы о том, что можно найти поток, который действительно достигает величины V. По любой заданной сети со значением V минимального сечения можно построить приведенную сеть, обладающую следующими свойствами:

1) граф приведенной сети есть граф исходной сети, за исключением, быть может, того, что несколько ребер исходной сети отсутствуют (нулевая пропускная способность) в приведенной сети;

2) каждое ребро в приведенной сети имеет пропускную способность, не большую, чем у соответствующего ребра исходной сети;

3) каждое ребро приведенной сети входит по крайней мере в одно сечение со значением V, причем V есть минимальное значение сечения приведенной сети.

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

Далее, возьмем любое другое ребро, не входящее ни в какое минимальное сечение, и выполним ту же самую операцию. Продолжим этот процесс до тех пор, пока не останется ребер, не входящих в какое-нибудь минимальное сечение. Ясно, что полученная сеть удовлетворяет требуемым условиям. Вообще говоря, имеется несколько различных приведенных сетей, которые можно получить из данной сети в зависимости от того порядка, в котором выбираются ребра. Если искомый поток можно найти в приведенной сети, то ясно, что тот же самый поток будет искомым и в исходной сети, потому что как условие Кирхгофа, так и условие ограничения пропускной способности будут выполнены. Следовательно, если доказать теорему для приведенных сетей, то она будет вообще справедлива.

Доказательство проведем индукцией по числу ребер. Заметим сначала, что если каждый путь через приведенную сеть содержит только два или меньшее число ребер, то эта сеть имеет вид, указанный на рис. 2.

Рис. 2.

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

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

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

Рис. 3,

Каждая из этих двух последовательных сетей содержит менее ребер. Это следует из наличия пути из левого полюса в правый длины по крайней мере три. Наличие этого пути влечет за собой существование ребра в левой части, которое не встречается в правой части, и наоборот. Таким образом, по индуктивному предположению можно создать искомый суммарный поток в каждой из этих сетей. Очевидно, что когда общая вершина разъединена и сеть возвращена к своему первоначальному вйду, то тот же самый поток останется неизменным и в исходной сети. Этим завершается доказательство.

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

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

эти входы 2, 3 и 6 единиц потока. Вершины справа — выходы, и желательно через эти вершины передать 3 и 8 единиц потока. Задача состоит в том, чтобы найти условия, при которых это возможно.

Эту задачу можно свести к предыдущей соединением входных каналов в общий левый узел и соединением выходных каналов в общий правый узел. В нашем частном случае это приводит к сети, изображенной на рис. 4. Сеть, полученная таким образом из первоначальной сети, будет называться расширенной сетью.

Рис. 4

Легко показать, что необходимые и достаточные условия для существования решения этой задачи с несколькими входами и выходами состоят в следующем:

1) сумма V входных потоков равна сумме выходных потоков;

2) минимальное сечение в расширенной сети имеет значение V.

Чтобы доказать это, заметим, что необходимость первого условия очевидна, а необходимость второго следует из предположения, что поток в первоначальной сети удовлетворяет условиям задачи. Этот поток можно преобразовать в поток расширенной сети и использовать теорему, из которой вытекает отсутствие сечений со значением, меньшим V. Так как имеются сечения со значением V, проходящие через присоединенные ребра, то значение минимального сечения равно V.

Достаточность этих условий следует из того замечания, что условие 2) благодаря доказанной теореме означает возможность создания в расширенной сети потока слева направо со значением V. Далее по закону Кирхгофа для правого и левого полюсов, используя условие 1), получим, что каждое присоединенное входное и выходное ребро несет поток, равный искомому. Следовательно, это же распределение потока в первоначальной сети решает поставленную задачу.