Природа потоков в сетях и принцип их сохранения

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

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

Определение. Потоком в сети S=(N, U) от входа s е N к выходу t е N называется неотрицательная функция ф, определенная на множестве дуг сети t/, со следующими свойствами:

• 1) величина потока по каждой дуге не должна превосходить ее пропускной способности 0 < ф(i₉j) < c (i, j), (ij) е U;
• 2) величина потока, входящего в каждую вершину сети, за исключением входа и выхода, равна величине потока, выходящего из этой вершины:

где Nj — множество вершин, инцидентных дугам, направленным от вершины i (исходящие); JV, — множество вершин, инцидентных дугам, направленным к вершине i (входящие).

Из определения потока следует, что величина потока не исчезает и не накапливается в вершинах сети, и, следовательно, количество потока, выходящего из входа 5, равно количеству потока, заходящему в выход t. Это значение называется величиной потока V. Таким образом, поток в сети сохраняется, а величина потока равняется сумме значений потоков, выходящих из вершины s или входящих в вершину t

На рис. 4.10 изображена сеть автомобильных потоков, которая представляет собой ориентированную сеть S = (N, U),

Рис. 4.10.

имеющую множество вершин N = {1, 2, 3, 4} и множество дуг ?/={(1,2); (2, 3); (2, 4); (1,3); (3,4)}.

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

с=Ы

Для ориентированной сети на рис. 4.10 матрица смежности имеет вид.

Матрица инциденций ориентированной сети на рис. 4.10 имеет следующий вид:

На рис. 4.10 стрелками показано направление одностороннего разрешенного движения потоков автомобилей. От одного перекрестка i до другого j пропускная способность по дуге по каждой улице c (i, j) ограничена и определяется максимально допустимой скоростью движения, например 60 км/ч.

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

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

Для источника сети при i = s нет входящих потоков, следовательно,.

Для стока при i = t нет выходящих потоков, следовательно,.

Рассмотрим пример анализа ориентированной сети S = = (N, Ц)_у представленной на рис. 4.11, N = {5, 1, 2, 3, 4, ?}; U = = {(*, 1); (5, 3); (1, 2); (1, 3); (2, t); (3, 2); (3, 4); (4,?)}.

Пропускная способность указана над каждой дугой, где рядом в скобках указано значение существующего потока. Свойства потока в данном случае выполняются, поскольку указанные величины не превышают пропускных способностей дуг. В каждой вершине, отличной от входа и выхода, поток сохраняется. Например, в вершину 2 заходят 4 ед. потока по дугам (1, 2) и (3, 2) и выходят 4 ед. по дуге (2, t). Величина потока в сети составляет Р=3 + 4 = 7и сохраняется.

Рис. 4.11.