Дискретная математика. Прокушев Л.А. - 13 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

11
Раздел 5. Основные понятия для ориентированного графа
Абстрактное описание орграфа; отображение инцидентности и
смежности; части графа; перемещения в орграфе; разновидности орг-
рафов; орграфы и бинарные отношения; транзитивные замыкания;
связность орграфа.
Литература: [1, c. 23–35].
Орграф G можно определить как совокупность G = (V, U ), где V =
={v
1
, …, v
n
} – множество вершин графа, а U ⊂ V
× V – конечное подмно-
жество упорядоченного (декартова) произведения, образующее множе-
ство дуг графа.
Дугу (стрелку), соединяющую вершины v
i
, v
j
, обозначают (v
i
, v
j
), где
v
i
– начало дуги, а v
j
– конец дуги. Говорят, что дуга направлена от
вершины v
i
к вершине v
j
или дуга исходит из вершины v
i
и входит в
вершину v
j
. Для удобства дуги также обозначают одной буквой: u
ij
=
=(v
i
, v
j
), u
k
= (v
i
, v
j
) или u = (v
i
, v
j
).
Пусть задан граф G = (V, U) и подмножество V
1
⊂ V. Говорят, что
дуга u = (v
i
, v
j
) заходит в V
1
, если v
i
∉V
1
, а v
j
∈V
1
(конец дуги v
j
находится в V
1
). Если v
i
∈V
1
, а v
j
∉V
1
, то говорят, что дуга исходит из
V
1
(начало дуги v
i
находится в V
1
). В обоих случаях дугу u называют
инцидентной подмножеству V
1
. Если подмножество сводится к одной
вершине, то дугу называют инцидентной этой вершине (заходящей в
нее или исходящей из нее).
Обозначим через Гv подмножество вершин V, смежных с v, в кото-
рые можно прийти по инцидентным дугам (стрелки исходят из v), или
иначе подмножество концов дуг, имеющих началом вершину v. По мат-
рице смежности S можно выделить подмножество Гv
i
по i-й строке, где
ненулевые элементы s
ij
указывают на вершины v
j
∈ Гv
i
. Это отображе-
ние инцидентности и смежности позволяет определить граф как пару
G = (V, Г), образованную множеством вершин V и многозначным ото-
бражением Г множества V в себя. Элемент v
i
∈ V называют вершиной, а
пару (v
i
, v
j
), где v
j
∈ Гv
i
, – дугой. Граф G имеет порядок n, если число
вершин V= n.
Обозначим через Г
-1
v подмножество вершин, смежных с v, из кото-
рых можно зайти в вершину v по инцидентным дугам, при этом матри-
ца смежности графа G
-1
= (V, Г
-1
) образуется транспонированием (пере-
становкой строк и столбцов) матрицы смежности графа G.

Страницы