ТРАНСПОРТНЫЕ СЕТИ
ОСНОВНЫЕ ПОНЯТИЯ
Сетью называется всякий ориентированный граф, в котором выделены две вершины I и S, называемые соответственно истоком и стоком сети. Из истока сети I ориентированные ребра только выходят, а в сток S ориентированные ребра только входят. Остальные вершины сети называются внутренними вершинами.
Будем считать, что каждая из внутренних вершин имеет как входящие, так и выходящие ребра.
ОПРЕДЕЛЕНИЕ
Граф G = (V, U), каждому ребру u Î U которой приписано неотрицательное вещественное значение c (u), называется транспортной сетью.
Отображение c:U ® R+ называется функцией пропускной способности ребер сети. Содержательно эта функция указывает на количество или объем определенного измеримого ресурса, который может передаваться по ребрам, соединяющим пары вершин сети.
Транспортная сеть, задаваемая сетью G, и функцией пропускной способности ребер c: U ® R+, обозначается как
N = (G, c).
Рассмотрим несколько примеров транспортных сетей.
1. Система железных дорог между двумя регионами, один из которых производит ресурсы, а другой их потребляет, может рассматриваться как транспортная сеть.
В этой сети исток и сток соответствуют производителю и потребителю ресурса.
Внутренние вершины сети представляют узлы железной дороги, являющиеся пересечениями нескольких дорог или концами отдельных участков таких дорог.
Ребра сети - это участки дорог. Пропускная способность ребер соответствует максимальному количеству ресурса, которое может одновременно передаваться по этим участкам.
2. Сеть обработки первичной информации. Такая сеть может служить моделью системы, в которой осуществляется передача информационного потока. Такая сеть позволяет извлекать из входного потока данных значимую информацию, осуществлять ее обработку а затем передавать её потребителям, используя для этого существующую систему каналов связи.
Исток и сток такой сети являются узлами, в которых информация соответственно поступает в сеть из внешней среды и передается во внешнюю среду в переработанном виде.
Ребра сети указывают очередность в переработке информации, а пропускная способность ребер задает максимальное количество информации, которое в состоянии переработать узел обработки, являющийся началом ребра, и передать в вершину - конец ребра.
Дальнейшее рассмотрение транспортных сетей ограничено только такими сетями, в которых все ребра являются ориентированными. Тогда ресурсы по каждому ребру сети могут передаваться лишь в одном направлении.
ОПРЕДЕЛЕНИЕ
Потоком в транспортной сети N = (G, c) называется всякая функция y: U ® R+, для которой выполнены условия:
1) " u Î U (0 £ y (u) £ c (u));
2) " v Î V 
.
Здесь 
(v) - множество ребер, выходящих из вершины v, а 
(v) - множество ребер, ведущих в эту вершину.
Значение y(u) для произвольного ребра u называется величиной потока, проходящего по этому ребру.
Тогда условие 1 приведенного определения означает, что величина потока по любому ребру транспортной сети не превосходит пропускной способности этого ребра.
Второе из приведенных условий означает, что суммарный поток, приходящий в произвольную внутреннюю вершину сети, равен суммарному потоку, выходящему из этой вершины.
Величиной потока y в транспортной сети N называется суммарный поток, выходящий из истока I. Величина потока y в транспортной сети N обозначается как y(N).
Условие 2 в определении потока для транспортной сети гарантирует, что значение y(N) равно суммарной величине потока, поступающего на сток сети. Доказательство этого факта содержится в следующей теореме.
ТЕОРЕМА 6.1
Для всякого потока y транспортной сети N = (G, c) справедливо равенство 
.
Доказательство
Возможны следующие случаи.
Случай 1. В сети N нет циклов, по всем ребрам которых проходит ненулевой поток.
В этом случае удалим из N все такие ребра, по которым проходит нулевой поток. Тогда полученный в результате граф будет подобен графу, приведенному на рис. 6.1. В таком графенет циклических ребер, а всякий путь может быть продолжен до пути, ведущего в S.
 |
I S
Рис. 6.1
Построим специальное представление графа G, разместив всякую его вершину в ярусе, определяемом значением максимальной длины путей, ведущих от истока сети к этой вершине.
Для приведенного примера сети, размещение вершин по ярусам имеет вид (рис 6.2)
I S
 |
0 1 2 3 4
(номера ярусов) Рис 6.2
Если в полученном представлении некоторое ребро соединяет вершины из не соседних ярусов, то разобьем его на несколько, вводя дополнительные вершины.
Для рассматриваемого графа G это приводит к следующему его представлению (рис. 6.3):
 |
I S
Рис. 6.3
На этом рисунке светлыми кружками выделены добавленные вершины. Ребрами этого графа представляются только вершины соседних ярусов. При этом пропускные способности и величины потока в добавленных ребрах совпадают с этими же значениями для разбиваемых ребер.
Очевидно, что величина потока в полученной сети совпадает с величиной потока в исходной сети. Кроме того, суммарные величины входного и выходного потоков для всякого внутреннего яруса сети равны. Поэтому суммарный выходной поток истока сети, является входным потоком вершин первого, второго и последующих ярусов.
Следовательно, .
Случай 2. Пусть в G имеются элементарные циклы ненулевой длины, через каждое ребро которых проходит ненулевой поток.
Покажем, что в этом случае ресурс, циркулирующий по всякому такому циклу, не влияет на величины каждого из двух суммарных потоков: выходящего из I и входящего в S.
Преобразуем y так, чтобы, сохранив величину потока, проходящего по сети, добиться отсутствия в сети N циклов с ненулевыми потоками в ребрах.
Для этого, пока в G имеются циклические ребра, будем повторять следующие действия.
1. В графе G возьмем произвольный элементарный цикл C, по всем ребрам которого протекает ненулевой поток.
2. Найдем значение d = min (y(u 1),..., y(ur)), где u 1,..., ur - ребра C.
3. Изменим функцию y, уменьшив ее значения для ребер C на величину d и оставив значения y для остальных ребер без изменения.
Поскольку для каждого повторения действий 1 - 3 в графе появляется новое ребро, по которому течет нулевой поток, то преобразование потока y заканчивается за конечное число шагов.
Исходный поток y преобразуется в функцию y*, которая также является потоком.
Кроме того, суммарные входные потоки для S (суммарные выходные потоки из I) для функций y и y* являются равными, поскольку через I и S в G не проходит ни один элементарный цикл ненулевой длины.
Поскольку окончательный поток удовлетворяет условиям случая 1, то для него выполняется доказываемое равенство:
.
Поэтому такое же равенство выполняется и для исходного потока:
.
Доказательство окончено.
Пример. Рассмотрим транспортную сеть, приведенную на рис. 6.4.
10 (5)
 |
14 (10) 17 (5) 2 (1) 9 (4)
I 7(6) S
5 (8)
11 (7) 16 (7) 10 (8)
9 (8) 24 (1)
Рис. 6.4
Здесь ребрам сети приписаны значения их пропускных способностей, в скобках указаны значения потока по ребрам сети.
Величина потока, приведенного на рис. 6.4, равна 18.
В общем случае величина потока в сети задает суммарное количество ресурса, передаваемого по сети от истока к стоку.
МАКСИМАЛЬНЫЕ ПОТОКИ
Среди различных потоков, которые могут быть определены для заданной транспортной сети, особый интерес представляют такие потоки, величина которых является наибольшей.
ОПРЕДЕЛЕНИЕ
Поток y транспортной сети N = (G, c) называется максимальным потоком, если y(N) = 
,
где F - множество всех потоков в сети N.
Ребро u сети N = (G, c), для которой задан поток y, называется полностью нагруженным, если y(u) = c (u).
ОПРЕДЕЛЕНИЕ
Поток y транспортной сети N = (G, c) называется полным потоком, если всякий путь в N, ведущий из I в S, содержит хотя бы одно полностью нагруженное ребро.
Упражнение.
1. Показать, что всякий максимальный поток является полным потоком.
2. Привести примеры транспортных сетей, имеющих единственный максимальный поток, несколько разных максимальных потоков. Может ли множество максимальных потоков транспортной сети быть бесконечным?
Напомним, что если W - путь в некотором графе, то E (W) обозначает множество ребер этого пути.
Для построения полного потока в произвольной транспортной сети N = (G, c), где G = (V, U), можно воспользоваться приводимым ниже методом насыщения дуг.