Математическое моделирование на графах. Часть 1. Берцун В.Н. - 24 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

24 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Ориентированным графом⎯G = (X, Г) называется множество X,
не обязательно конечное, рассматриваемое вместе с некоторым ото-
бражением Г: X → X, которое может не быть однозначным. Элемен-
ты множества X (или точки) называются вершинами орграфа⎯G, а
пара вершин (x, y) называется дугой, если y = Гx. Точка x в этом слу-
чае – начало дуги (предшествующая вершина), а точка y – конец ду-
ги (последующая вершина)[1 – 3]. Например, в орграфе⎯G на
рис. 1.27 изображено 10 дуг для числа вершин n = 5.
{}{}{}
{} {}
{}
123 4 5 1 245 2 23
345 4 15 51
, , , , , , , , , ,
, , , , .
Xxxxxx
Г
xxxxГx xx
Гx x x Гx x x Гx x
===
== =
Две вершины называются смежными, если они соединены дугой,
а две дуги смежные, если у них общая вершина. Например, на
рис. 1.27 вершины x
1
, x
2
и дуги u
1
, u
3
являются смежными.
u
2
x
2
u
3
u
9
u
7
u
8
u
6
u
10
u
5
u
1
u
4
x
5
x
4
x
3
x
1
Рис. 1.27
Говорят, что вершина x и дуга графа u являются инцидентными,
если вершина x есть начало или конец этой дуги. На рис. 1.27 вер-
шина x
1
инцидентна дуге u
1
, а вершина x
5
не инцидентна дуге u
3
.
Полустепенью исхода (степенью выхода) µ вершины А орграфа
называется число выходящих из А дуг, а полустепенью захода (сте-

Страницы