6. Транспортные сети

6.1. Основные понятия

Сетью называется всякий ориентированный граф, в котором выделены две вершины 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) называется всякая функция : U  R⁺, для которой выполнены условия:

1) u  U (0   (u)  c(u));

2) v  V .

Здесь (v)  множество ребер, выходящих из вершины v, а (v)  множество ребер, ведущих в эту вершину.

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

Тогда условие 1 приведенного определения означает, что величина потока по любому ребру транспортной сети не превосходит пропускной способности этого ребра.

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

Величиной потока  в транспортной сети N называется суммарный поток, выходящий из истока I. Величина потока  в транспортной сети N обозначается как (N).

Условие 2 в определении потока для транспортной сети гарантирует, что значение (N) равно суммарной величине потока, поступающего на сток сети. Доказательство этого факта содержится в следующей теореме.