Составители:
Рубрика:
14
Степень вершины обозначают через deg v
i
.
Для орграфа deg v
i
= d
+
(v
i
) + d
–
(v
i
).
Определение 1.10. Граф, степени всех k вершин
которого одинаковы, называется однородным
гра-
фом
степени k.
Определение 1.11. Дополнением данного графа
называется граф, состоящий из всех ребер и их
концов, которые необходимо добавить к исходно-
му графу, чтобы получить полный граф.
Для ориентированного графа множество
вершин, в которые ведут дуги, исходящие из вер-
шины х, обозначают G (х), то есть
G (х) = {y:.(x,.y)
∈
.G}.
Множество G.(x) называют образом
вершины x.
Соответственно G
.–1
(у) – множество вершин, из
которых исходят дуги, ведущие в вершину у,
G
.–1
(y) = {x: (x, y)
∈
G}.
Множество G
.–1
(у) называют прообразом вершины y.
Пример 1.4.
В графе, изображенном на рис. 2, концами
ребра a
1
являются вершины x
1
, x
2
; вершина x
2
ин-
цидентна ребрам a
1
, a
2
; степень вершины x
3
равна
3; вершины x
1
и x
3
смежные; ребра a
1
и a
2
смеж-
ные; вершина x
4
висячая. В ориентированном гра-
фе, изображенном на рис. 3, началом дуги a
1
явля-
ется вершина x
1
, а ее концом – вершина x
2
; верши-
163
01100
10000
10011
00100
00100
⎡
⎤
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎣
⎦
5. Неориентированный граф G задан вершинами
{1,2,3,4,5,6,7} и рёбрами
{(1,3); (1,4); (1,5); (1,7); (2,3); (2,4); (2,7);
(3,5); (3,7); (4,6); (4,7); (5,6); (6,7)}.
Построить реализацию графа, найти цикломатиче-
ское число и его остов.
Контрольная работа №2
1. Представить в виде ориентированного графа от-
ношение
ρ = (V, E),V = {2, 4, 16, 22},
E = {(х, у) : (х + у) / 6}.
2. Ориентированный граф G c множеством вершин
V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг
{(1, 2), (1, 4), (1, 5), (2, 4), (3, 2), (3, 4),
(3, 4), (4, 2), (4, 5), (5, 5),(5, 7), (7, 1)}.
Построить реализацию графа, матрицу инцидент-
ности и матрицы соседства вершин для ориенти-
Степень вершины обозначают через deg vi. ⎡0 1 1 0 0⎤
Для орграфа deg vi = d + (vi) + d – (vi). ⎢1 0 0 0 0⎥
Определение 1.10. Граф, степени всех k вершин ⎢ ⎥
⎢1 0 0 1 1⎥
которого одинаковы, называется однородным гра- ⎢ ⎥
фом степени k. ⎢0 0 1 0 0⎥
Определение 1.11. Дополнением данного графа ⎢⎣ 0 0 1 0 0 ⎥⎦
называется граф, состоящий из всех ребер и их
концов, которые необходимо добавить к исходно- 5. Неориентированный граф G задан вершинами
му графу, чтобы получить полный граф. {1,2,3,4,5,6,7} и рёбрами
Для ориентированного графа множество {(1,3); (1,4); (1,5); (1,7); (2,3); (2,4); (2,7);
вершин, в которые ведут дуги, исходящие из вер- (3,5); (3,7); (4,6); (4,7); (5,6); (6,7)}.
шины х, обозначают G (х), то есть
G (х) = {y:.(x,.y) ∈.G}. Построить реализацию графа, найти цикломатиче-
Множество G.(x) называют образом вершины x. ское число и его остов.
Соответственно G.–1(у) – множество вершин, из Контрольная работа №2
которых исходят дуги, ведущие в вершину у,
G.–1(y) = {x: (x, y) ∈ G}. 1. Представить в виде ориентированного графа от-
Множество G.–1(у) называют прообразом вершины y. ношение
ρ = (V, E),V = {2, 4, 16, 22},
Пример 1.4. E = {(х, у) : (х + у) / 6}.
В графе, изображенном на рис. 2, концами 2. Ориентированный граф G c множеством вершин
ребра a1 являются вершины x1, x2; вершина x2 ин- V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг
цидентна ребрам a1, a2; степень вершины x3 равна
3; вершины x1 и x3 смежные; ребра a1 и a2 смеж- {(1, 2), (1, 4), (1, 5), (2, 4), (3, 2), (3, 4),
ные; вершина x4 висячая. В ориентированном гра- (3, 4), (4, 2), (4, 5), (5, 5),(5, 7), (7, 1)}.
фе, изображенном на рис. 3, началом дуги a1 явля-
Построить реализацию графа, матрицу инцидент-
ется вершина x1, а ее концом – вершина x2; верши-
ности и матрицы соседства вершин для ориенти-
14 163
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
