Потоки в сетях

Деятельность современного общества тесно связана с разного рода сетями — возьмите, к примеру, транспорт, коммуникации, распределение товаров и тому подобное. Поэтому математический анализ таких сетей стал предметом фундаментальной важности.

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

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

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

Изучение максимальных потоков через сеть тесно связано с понятием разреза, т.е. такого множества дуг орграфа , которое обладает тем свойством, что любая простая орцепь из в проходит через дугу, принадлежащую . Другими словами, разрезом в сети является не что иное, как — разделяющее множество соответствующего орграфа . Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Мы будем рассматривать главным образом такие разрезы, которые обладают наименьшей возможной пропускной способностью, — так называемые минимальные разрезы.

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

Теорема (о максимальном потоке и минимальном разрезе). Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза.

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

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

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

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

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

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

• оно не превышает ни одного из чисел, необходимых для насыщения дуг первого типа;
• оно не превышает потока через любую из дуг второго типа.

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

Для завершения доказательства обозначим через множество всех дуг вида , где принадлежит , а принадлежит . Ясно, что является разрезом. Более того, мы видим, что каждая дуга из насыщена, так как в противном случае вершина также принадлежала бы Следовательно, пропускная способность множества должна равняться величине потока , а поэтому и есть искомый разрез.

Приложение

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

Шаг 1. Сначала подберем поток , обладающий ненулевой величиной (если такой поток существует). Стоит отметить, что чем больше величина выбранного нами начального потока , тем проще будут последующие шаги.

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

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