Графы и сети. Харитонова Е.В. - 33 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

32
2. СЕТИ
2. 1. Сети и потоки
Сеть можно представить как систему, транспортирующую некий продукт
из одной точки в другую. Этим продуктом могут быть люди, электроэнергия,
природный газ, нефть и многое другое. Примером может служить система неф-
тепровода, где нефть течет из одной точки к другим точкам системы. Наша
терминология будет
соответствовать данной концепции. Используя такое пред-
ставление, рассмотрим сеть как ориентированный граф, ребра которого – трубы
между точками системы, а они, в свою очередь, представлены вершинами гра-
фа. Каждому ребру e = (υ
i
, υ
j
) соответствует положительное число c(e), назы-
ваемое пропускной способностью e. Если между двумя вершинами не сущест-
вует ребра, то пропускную способность полагаем равной нулю. В примере с
нефтяными сетями пропускная способность связана с количеством нефти, про-
ходящей через трубу (ребро).
Перед тем как определить сеть, ограничим определение ориентированно-
го графа. Наличие
петель у графа недопустимо, поскольку рассматриваемые за-
дачи связаны только с транспортировкой продукта между различными точками.
Будем считать, что если существует ребро из υ
i
в υ
j
, то нет ребра из υ
j
в υ
i
. Та-
ким образом, рассматривается поток продукта только в одну сторону. Необхо-
димое требование: ориентированный граф должен быть связан, т.к. если имеет-
ся путь из
а в z, нас будет интересовать только компонента, содержащая a и z.
Если между
a и z не существует пути, то и определять нечего. Ориентирован-
ный граф, удовлетворяющий этим условиям, часто называется простым связ-
ным ориентированным графом. Назовем такой граф ориентированным графом,
имея в виду, что он удовлетворяет упомянутым выше ограничениям. Рассмот-
рим также особую вершину
a , называемую источником, и особую вершину z,
называемую стоком. Степень входа вершины
a равна 0, так что в источник ни-
что не втекает. Степень выхода вершины z равна 0, так что из стока ничто не
вытекает. Таким образом, продукт перевозится из
a и имеет место назначения
z. Более точно определим сеть следующим образом.
● Сеть – это ориентированный граф (G, V, E) вместе с весовой функцией
C : E → N и выделенными вершинами
a ,
z
, такими что
(
)
(
)
() ()
0. zinteg ii
0; ainteg i
=
=
Например, граф, изображенный на рис. 2.1, является примером сети, где числа на ка-
ждом ребре обозначают пропускную способность.

Страницы