 |
 |
 |
 |
|
 |
 |
67
Геометрически граф может быть представлен в виде множества точек (изображающих вершины) и
соединяющих их линий (со стрелками), соответствующих ребрам (дугам) (рис. 3.3, 3.4). Очевидно, что с
каждым ориентированным графом можно однозначно связать неориентированный, заменив дуги на
ребра. Если любые две вершины графа соединяются не более чем одной дугой (ребром), то граф
называется простым и может быть задан с помощью пары (I, D). В этом случае каждая дуга (ребро) d
полностью определяется парой соединяемых вершин (i, j), что условно записывается в виде:
d=(i,j).
Упорядоченная пара вершин (i, j), которая ставится в соответствие некоторой дуге d, задает ее
ориентацию: i называется началом дуги, а
j
— ее концом, а сама дуга считается инцидентной данным
вершинам.
Путем длины п в ориентированном графе (I,
D) называется упорядоченная последовательность
различных дуг (d1, d2,..., d
n
), для которых начало каждой последующей совпадает с концом предыдущей.
Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.
Для неориентированного графа аналогом понятия путь является цепь, а контура — цикл.
Если две любые вершины неориентированного графа могут быть соединены цепью, то он называется
связным. Ориентированный граф называется связным, если ему отвечает связный неориентированный
граф.
Связный неориентированный граф, не содержащий циклов, называется деревом.
Если Y ? D, а отображение G
Y
является сужением отображения G на множество Y, то граф (I, Y, G
Y
)
называют частичным графом (реберным подграфом) графа (I, D, G).
Рассмотрим задачу: имеется конечный граф (I, D, G), каждой вершине i которого сопоставлено
некоторое число b
i
, называемое интенсивностью вершины. Граф (I, D, G), вершинам которого
сопоставлены значения интенсивностей b
i
, будем называть сетью. Если b
i
> 0, то вершина i называется
источником, если b
i
< 0, то —
стоком, а если b
i
= 0, то —
нейтральной вершиной. Множество
источников, стоков и нейтральных вершин обозначим соответственно I
+
, I
-
,
I
0
.
Для определенной выше сети потоком называется такая совокупность величин, заданных на
множестве дуг, Х={х
d
}
d
?
D
,
что
где D
i
+
— множество дуг, исходящих из вершины i, a D
i
-
— множество дуг, входящих в нее.
Величина х
d
называется значением потока по дуге d и содержательно интерпретируется как количество
продукта, пропускаемого по данной дуге.
Соотношение (3.11) означает, что для любой вершины сети разность выходящего и входящего
потоков равна ее интенсивности.
На базе введенной терминологии может быть сформулировано много различных задач. Рассмотрим
наиболее известные из них. Для каждой дуги d?D определим значения c
d
? 0,
называ
емые стоимостью
перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид