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

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

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

   1. V= {v₁,v₂,v₃,v₄,v₅},E={(v₁,v₅),(v₁,v₃),(v₃,v₅),(v₃,v₄),(v₁,v₄)}

   2. V= {v₁,v₂,v₃,v₄,v₅},E={(v₁,v₂),(v₁,v₅),(v₂,v₅),(v₃,v₄),(v₅,v₄)}

   3. V= {v₁,v₂,v₃,v₄,v₅},E={(v₅,v₂),(v₁,v₃),(v₄,v₅),(v₅,v₄),(v₃,v₄)}

   4. V= {v₁,v₂,v₃,v₄,v₅},E={(v₄,v₂),(v₁,v₃),(v₁,v₅),(v₃,v₁),(v₅,v₄)}

   5. V= {v₁,v₂,v₃,v₄,v₅},E={(v₅,v₂),(v₁,v₃),(v₄,v₁),(v₃,v₄),(v₁,v₄)}

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

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

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

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

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

8. Выполнить пересечение графов G₁= {V₁,E₁}, гдеV₁= {v₁,v₂,v₃,v₄,v₅}E₁= {(v₁,v₃),(v₂,v₄),(v₃,v₅)} иG₂= {V₂,E₂}, гдеV₂= {v₆,v₇,v₈,v₃,v₅}E₁= {(v₃,v₅),(v₆,v₈),(v₃,v₇)}

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

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

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

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

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

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

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

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

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

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