Введение в информационные системы. Брюхомицкий Ю.А. - 58 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

58
а б
Рис. 5.2. Ориентированный (а) и смешанный (б) графы
Обратно, любой неориентированный или смешанный граф всегда мож-
но преобразовать в ориентированный граф заменой каждого ребра парой не-
строго параллельных дуг.
Если заменить направления всех дуг орграфа на противоположные, по-
лучим орграф, обратный к исходному.
Если множество вершин
графа – конечно, то он называется конечным
графом. В математике рассматриваются и бесконечные графы, но в моделирова-
нии данных они обычно не применяются. Конечный граф G = (V, E), содержа-
щий р вершин и q ребер, называется (p,q)-графом.
Пусть V = {v
1
, v
2
, …, v
р
} и E = {e
1
, e
2
, …, e
q
} – соответственно множест-
ва вершин и ребер (p,q)-графа. Каждое ребро e
k
E соединяет пару вершин v
i
,
v
j
V, являющихся его концами (граничными вершинами). Для ориентирован-
ного ребра (дуги) различают начальную вершину, из которой дуга выходит и
конечную вершину, в которую дуга заходит. Ребро, граничными вершинами ко-
торого является одна и та же вершина называется петлей. Ребра с одинаковыми
граничными вершинами являются параллельными и называются кратными. В
общем случае граф может содержать и изолированные вершины, которые не
являются концами ребер и не связаны ни между собой, ни с другими вершина-
ми. Например, для (5, 6)-графа, показанного на рис. 5.3, V = {v
1
, v
2
, v
3
, v
4
,
v
5
}; E =
{e
1
, e
2
, e
3
, e
4
, e
5
, e
6
}; ребра e
2
и e
3
, ребро e
6
является петлей, а v
4
– изолированная
вершина.
Число ребер, связанных с вершиной v
i
(петля учитывается дважды), на-
зывают степенью вершины и обозначают через (v
i
) или deg (v
i
). Так, для графа
на рис. 5.3. (v
1
) = 1, (v
2
) = 4 и т.д. Степень изолированной вершины равна
нулю ((v
4
) = 0). Вершина степени 1 называется концевой или висячей верши-
ной ((v
1
) = 1). Легко показать, что в любом графе сумма степеней всех вершин
равна удвоенному числу ребер, а число вершин нечетной степени всегда четно.
В орграфе различают положительные
+
(v
i
)и отрицательные
-
(v
i
) степени
вершин, которые равны соответственно числу исходящих из v
i
и заходящих в v
i
дуг.

Страницы