|
Сходство сетевых представлений наблюдается в природе, технике и различных сферах деятельности человека. Так, например, с высоты птичьего полета или самолета можно наблюдать сетевую модель формирования реки, например Волги от ее истоков маленькие ручейки и реки, соединяясь во взаимосвязанные артерии, объединяются в одно большое русло, по которому потоки воды устремляются в Каспийское море. Такие же аналогии представляют собой сети железных дорог, по которым транспортные потоки направляются из пунктов отправления в пункты назначения, осуществляя перевозку потоков грузов и пассажиров. Совокупность линии электропередач так же представляют собой вместе энергетическую сеть, по которой потоки электроэнергии от электростанций по проводам поступают к потребителям. Автомобильные дороги как в масштабе города, района, области, так и в более крупных масштабах страны или, например, части света -Европы представляют собой сети, по которым движутся потоки автомобилей. Нефте- и газопроводы в совокупности представляют собой сети трубопроводов, по которым потоки нефти или газа поступают от источников к потребителям. Водопроводные сети обеспечивают движение потоков воды по трубопроводам от источников к потребителям. Аналогичные сети представляют собой маршруты движения кораблей и самолетов, обеспечивающие перемещение потоков пассажиров и грузов по планете. Такие же аналогии представляют собой телефонные, радио и телекоммуникационные сети, по которым циркулируют информационные потоки, например компьютерные сети связи различного назначения. Особый интерес представляют сети, образованные движением товарных и финансовых потоков, которые могут пояснить очень многие явления нашей жизни, поскольку они являются необходимыми для обеспечения жизни людей.
Перечисленные сетевые аналогии потоковых процессов имеют динамический характер, связанный с перемещениями различных по своей природе масс в пространстве: электроэнергии, нефти, газа, воды, воздуха, железнодорожного, воздушного, автомобильного транспорта, товаров, финансов, пешеходов, информации и т.п. Причем существование этих потоков необходимо для обеспечения и поддержания жизнедеятельности человека. Именно поэтому возник принцип сохранения потока. Сетевое представление взаимодействия и циркуляции потоков необходимо, чтобы оценить и вычислить разные характеристики, описывающие условия существования и поведения потоков в таких сетях. Множество возникающих в таких случаях задач может быть решено с помощью теории потоков в сетях. В этой теории в качестве основы рассматриваются движения в сетях потоков любой природы от источника s к стоку t.
Определение. Потоком в сети S = (N, U) от входа s N к выходу t N называется неотрицательная функция , определенная на множестве дуг сети U, со следующими свойствами:
1) величина потока, по каждой дуге не должна превосходить
ее пропускной способности 0 (i, j) c(i, j) (i, y) U ;
2) величина потока, входящего в каждую вершину сети, за исключением входа и выхода, равна величине потока, выходящего из этой вершины.
Из определения потока следует, что величина потока не исчезает и не накапливается в вершинах сети, и, следовательно, количество потока из входа s равно количеству потока, заходящему в выход t.
Представленная ориентированная сеть S = (N, U) имеет множество вершин N = {l, 2, 3, 4} и множество дуг U = {(1, 2) (2, 3) (2, 4), (1, З),(З, 4)}.
Количественные характеристики дуг сети, а также взаимосвязь между ее узлами могут быть представлены с помощью матрицы расстояний L = ||lij|| или матрицы стоимостей C = ||cij||,
От одного перекрестка i до другого / пропускная способность по дуге по каждой улице c(i, j) ограничена и определяется шириной улиц и максимально допустимой скоростью движения, например 60 км/ч. В связи с этим мощность автомобильного потока (i, j) не может превысить допустимую с(i, j). Таким образом выполняется первое свойство потока, условие существования статического или устойчивого потока для каждой улицы:
0(i,j)c(i,j) (i,j)U.
Пропускная способность указана над каждой дугой, где рядом в скобках указано значение потока. Свойства потока в данном случае выполняется. Указанные величины не превышают пропускных способностей дуг. В каждой вершине, отличной от входа и выхода, поток сохраняется. Например, в вершину 2 заходят 4 единицы потока по дугам (1,2) и (3,2) и выходят 4 единицы по дуге (2,t) Величина потока V = 3 + 4 = 7.
|
