Контрольное задание №1.

1. Задайте графическим и матричным способом ориентированный, неориентированный, смешанный граф.

2. Изобразите граф G = {V,E}, где

a. V= {v1,v2,v3,v4,v5}, E={(v1,v5),(v1,v3),(v3,v5),(v3,v4),(v1,v4)}

b.

c. V= {v1,v2,v3,v4,v5}, E={(v5,v2),(v1,v3),(v4,v5),(v5,v4),(v3,v4)}

d. V= {v1,v2,v3,v4,v5}, E={(v4,v2),(v1,v3),(v1,v5),(v3,v1),(v5,v4)}

e. V= {v1,v2,v3,v4,v5}, E={(v5,v2),(v1,v3),(v4,v1),(v3,v4),(v1,v4)}

3. Постройте матрицу для изображенного в предыдущем задании графа.

4. Постройте полный граф с 4 вершинами.

5. Постройте граф, изоморфный графу из первого задания.

6. Составьте словесный алгоритм определения маршрута в графе.

7. Составьте структурную схему алгоритма определения связности произвольного неориентированного графа.

8. Выполнить пересечение графов G1 = {V1,E1}, где V1 = {v1,v2,v3,v4,v5} E1= {(v1,v3),(v2,v4),(v3,v5)} и G2 = {V2,E2}, где V2 = {v6,v7,v8,v3,v5} E1= {( v3,v5),(v6,v8),(v3,v7)}

9. Доказать или опровергнуть:

a. объединение любых двух различных цепей, соединяющих две вершины, содержат простой цикл;

b. объединение любых двух различных простых цепей, соединяющих две вершины, содержит простой цикл.

10. Если d(u,v) = m в графе G, то чему равно d(u,v) в графе Gn?

11. Найти наибольшее число ребер в графе с pвершинами, не имеющем четных простых циклов.

12. Докажите, что если в графе G существуют пути между вершинами aи b, а также между bи c, то существует путь между aи c.

13. Докажите, что замкнутая цепь, все вершины которой имеют степень два, является циклом.

14. Докажите, что граф Gявляется связным тогда и только тогда, когда для каждого разбиения (V1, V2) множества Vс непустымиV1и V2 существует ребро в G, соединяющее вершину из V1с вершиной изV2.

15. Покажите, что простой граф G, имеющий по крайней мере две вершины, содержит две вершины одинаковой степени.

16. Существует ли два различных графа с одной и той же матрицей циклов? Покажите.