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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
Рис. 1.15
Пример. Орграф, у которого V = {a, b, c, d} и E = {(a, b), (b, c), (c, c), (b, d), (d, b), (c,
d), (d, a)} изображен на рис. 1.16.
Рис. 1.16
● Если (a, b) – ребро ориентированного графа G(V, E), так что a – началь-
ная вершина, a b – конечная вершина ребра (a, b) тогда вершины a и b инци-
дентны ребру (a, b). Вершина a называется смежной к вершине b. Вершина b
называется также смежной от вершины a.
● Степенью выхода вершины
υ называется количество ребер, для кото-
рых υ является начальной вершиной, обозначается outdeg(υ).
● Степенью входа вершины υ называется количество ребер, для которых
υ является конечной вершиной, обозначается indeg(u).
● Если indeg(υ) = 0, то вершина υ называется источником. Если outdeg(υ)
= 0, то вершина υ называется стоком.
Пример. В ориентированном графе на рис. 1.17, indeg(υ
0
) = 0, indeg(υ
1
) = 1, indeg(υ
2
) =
2, indeg(υ
3
) = 2, indeg(υ
4
) = 3, так же outdeg(υ
0
) = 3, outdeg(υ
1
) = 2, outdeg(υ
2
) = 2, outdeg(υ
3
) =
1, outdeg(υ
4
) = 0. Вершина υ
0
– источник, υ
4
– сток.
Рис. 1.17
● Ориентированный граф с более чем одним ребром из одной вершины в
другую называется мультиграфом или ориентированным мультиграфом.
υ
1
υ
0
υ
2
υ
4
υ
3
a
b
c
b c
a d

Страницы