Определение. Сетью называется всякий ориентированный граф, в котором выделены две вершины I и S, называемые соответственно истоком и стоком сети

ОСНОВНЫЕ ПОНЯТИЯ

ТРАНСПОРТНЫЕ СЕТИ

Сетью называется всякий ориентированный граф, в котором выделены две вершины I и S, называемые соответственно истоком и стоком сети. Из истока сети I ориентированные ребра только выходят, а в сток S ориентированные ребра только входят. Остальные вершины сети называются внутренними вершинами.

Будем считать, что каждая из внутренних вершин имеет как входящие, так и выходящие ребра.

Граф G = (V, U), каждому ребру u Î U которой приписано неотрицательное вещественное значение c (u), называется транспортной сетью.

Отображение c:U ® R⁺ называется функцией пропускной способности ребер сети. Содержательно эта функция указывает на количество или объем определенного измеримого ресурса, который может передаваться по ребрам, соединяющим пары вершин сети.

Транспортная сеть, задаваемая сетью G, и функцией пропускной способности ребер c: U ® R⁺, обозначается как
N = (G, c).

Рассмотрим несколько примеров транспортных сетей.

1. Система железных дорог между двумя регионами, один из которых производит ресурсы, а другой их потребляет, может рассматриваться как транспортная сеть.

В этой сети исток и сток соответствуют производителю и потребителю ресурса.

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

Ребра сети - это участки дорог. Пропускная способность ребер соответствует максимальному количеству ресурса, которое может одновременно передаваться по этим участкам.

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

Исток и сток такой сети являются узлами, в которых информация соответственно поступает в сеть из внешней среды и передается во внешнюю среду в переработанном виде.

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

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

Дата добавления: 2015-03-31