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

UptoLike

ВУЗ: 

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

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

Рубрика: 

30
4. С1 ∪ D.
5. С1 ∩ D.
6.
.
D
7. C1 \ D.
8. C1 ↓ D.
9. Показать отношение включения между множествами: C1, D, С1 ∪ D,
С1 ∩ D, C1 \ D, C1
↓
D.
Для пояснения пунктов 4–8 использовать диаграммы Эйлера-Венна.
Обработка ориентированного графа
Общие методические указания по обработке орграфа приведены
(разд. 5). Пусть орграф G = (V, U) состоит из множества вершин V =
={v
1
, v
2
, v
3
, v
4,
v
5
} и множества дуг U = {u
1
= (v
1
, v
2
), u
2
= (v
2
, v
1
), u
3
=
=(v
2
, v
3
), u
4
= (v
2
, v
3
), u
5
= (v
3
, v
3
), u
6
= (v
3
, v
4
), u
7
= (v
4
, v
1
), u
8
= (v
5
, v
4
),
u
9
= (v
5
, v
5
)}. Множество дуг можно для краткости задать также в виде
множества пар номеров начала и конца дуг: U = {(1, 2), (2, 1), (2, 3), (2,
3), (3, 3), (3, 4), (4, 1), (5, 4), (5, 5)}. Количество вершин графа n = |V| =
5, а количество дуг |U| = 9.
Геометрическое и матричное представление заданного графа приве-
дено на рис. 2. Орграф можно описать квадратной матрицей смежно-
сти S
nґn
, где n – количество вершин графа, а элемент s
ij
равен количе-
ству дуг (v
i
, v
j
), т. е. стрелок, идущих от вершины v
i
к v
j
.
Дуга может быть инцидентна не только вершинам, представляющим
ее начало и конец, но и множеству вершин. На рис.1 выделена область,
включающая подмножество вершин V
1
= {v
2
, v
3
} (V
1
М V). Говорят, что
дуга u = (v
i
, v
j
) заходит в V
1
, если конец дуги v
j
находится в V
1
, и дуга
u исходит из V
1
, если начало дуги v
i
находится в V
1
. В обоих случаях
дугу u называют инцидентной подмножеству V
1
, причем она должна
v
3
v
1
v
2
V
1
v
4
v
5
u
1
u
2
u
3
u
4
u
5
u
6
u
7
u
8
u
9
0 1 0 0 0
1 0 2 0 0
0 0 1 1 0
1 0 0 0 0
0 0 0 1 1
S
5×5
=
v
1
v
2
v
3
v
4
v
5
v
1
v
2
v
3
v
4
v
5
Рис. 2. Орграф и его матрица смежности

Страницы