2(1;U1) (1;u2) (1;u3)

u1 u2 u3

× =

1 (2;U1) (2;u2) (2;u3) Упражнения

Рис. 13 Рис. 14

Рис. 15

1. Для графов на рис.13 и 14 задать части H1 и H2 такие, что сумма H1 и H2 является прямой;

H1 и H2 не пересекаются по вершинам;

H1 и H2 не пересекаются по рёбрам.

2. Для графа G на рис.15:

1) определить является ли следующая часть Hi (i{1, 2, …, 5}) графа G подграфом, суграфом, покрывающим суграфом, если:

a) V(H1)={a, b, e, f}

Х(H1)={1, 3, 4, 6};

б) V(H2)={a, b, e, f}

Х(H2)={1, 3, 4, 5, 6, 13};

в) V(H3)={f, g, m, k}

Х(H3)={14, 15, 17, 18, 19, 20, 21, 22};

г) V(H4)={b, c, d, f, g, h}

Х(H4)={2, 7, 9, 11}

д) V(H5)=V(G)

Х(H5)={1, 2, 7, 8, 13, 16, 17, 18}

2) выполнить операции над H1, H2, H3 графа G

3. Пусть множество V={vi}, i=1, 2, 3, 4. На V задано отно­шение эквивалентности R так, что vj R vk, где j,k=1,2,3,4. Какому графу G соответствует отношение R? Задать G гра­фически.

4. Пусть граф содержит G V={v1, v2, v3, v4, v5}, X={( v1, v2),( v1, v5),( v2, v3),( v2, v4),( v3, v5)}, |V|=5, |Х|=5.

Задать граф G графически, а соответствующее ему отношение - матри­цей смежности. Каковы свойства данного отношения?

5. Изобразить графы, соответствующие отношениям, пред­ставленным следующими матрицами:

А б в

Г д

6. Докажите, что граф является пустым тогда и только тогда, когда все его подграфы – тоже пустые.

7.Постройте граф, изображающий отношение делимости на множестве

{1,2,3,4,5,6,7,8,9,10}.

8.Докажите, что граф является полным тогда и только тогда, когда все его подграфы, порождённые некоторым множеством вершин – тоже полные.

9.Докажите, что пустой граф с n вершинами содержит ровно n попарно неизоморфных подграфов.

10.Докажите, что граф с n вершинами является пустым тогда и только тогда, когда он содержит ровно n попарно неизоморфных подграфов.

11.Докажите, что граф с n вершинами является полным или пустым тогда и только тогда, когда он содержит ровно n попарно неизоморфных подграфов, порождённых некоторыми множествами вершин.

12.Докажите, что полный граф с n вершинами содержит ровно n попарно неизоморфных подграфов, порождённых некоторыми множествами вершин.

13.Докажите, что подграф H графа G является порождённым множеством своих вершин тогда и только тогда, когда не существует ни одного другого подграфа графа G, для которого H являлся бы остовным подграфом.

14.Заданы два графа G1 и G2. Выполнить G1 + G2, G1 - G2.

ребра	вершины
a	1,2
b	2,3
h	2,4
k	3,3

G2	a	b	c	d
1	1	0	0	0
2	1	1	1	0
3	0	1	0	1
4	0	0	1	1

G1

15. Получить декартово произведение графов.

× =

× =

× =

× =

16.Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.