Задачи и упражнения

1. Построить все попарно неизоморфные простые 4-вершинные графы.

2. Построить все попарно неизоморфные простые несвязные

5-вершинные графы, не имеющие изолированных вершин.

3. Построить все попарно неизоморфные 6-вершинные графы, состоящие:

1) из 4 компонент,

2) из 3 компонент,

3) из одной компоненты и имеющие 7 ребер и ровно 2 висячие вершины.

4. Сколько существует попарно неизоморфных простых 6-вершинных графов со следующим набором степеней вершин:

1) ;2) ;3) .

5.Для графов, полученных в задаче 4, построить матрицы смежности вершин и матрицы Кирхгофа.

6. Нарисуйте все связные попарно неизоморфные кубические графы (граф называется кубическим, если для любой его вершины ) на восьми вершинах.

7.Выяснить, какие наборы степеней вершин могут быть у простых связных 6-вершинных графов, имеющих 7 ребер, содержащих вершину степени 2 и вершину степени 3. Для каждого допустимого набора степеней вершин привести пример графа.

8.Показать, что в каждом простом графе, содержащем не менее двух вершин, найдутся 2 вершины с одинаковыми степенными.

9.Доказать, что для любого существует простой связный вершинный граф, содержащий вершин с неравными друг другу степенями.

10. Сколько существует попарно неизоморфных простых графов, имеющих

1) 6 вершин и 11 ребер;

2) 7 вершин и 18 ребер;

3) 8 вершин и 24 ребра;

4) 6 вершин, 6 ребер и 2 связные компоненты;

5) 8 вершин и удовлетворяющих условию: сумма степеней всех вершин не меньше 53?

11.Доказать: если графы и простые и имеют не более 4 вершин, то необходимым и достаточным условием их изоморфизма является совпадение наборов степеней вершин.

12.Среди пар графов, изображенных на рис. 37–40 указать пары изоморфных и неизоморфных графов.

Рис. 37

Рис. 38

Рис. 39

Рис. 40

Рис. 41

13. В графах, изображенных на рис. 40 и 41, найти подграфы, гомеоморфные .

14. Сколько существует попарно неизоморфных графов с 10 вершинами и 43 ребрами.

15. Выяснить, является ли последовательность (4,4,2,2,1,1) графической. (Последовательность называется графической, если существует граф с вершинами, степени которых равны ).

16. Какое наименьшее число ребер может иметь связный граф с p вершинами, не являющийся деревом?

17. Доказать, что у вершинного дерева число висячих вершин не меньше .

18. Верно ли, что если у графа число висячих вершин равно числу ребер, то граф – дерево?

19. Изобразить все попарно неизоморфные деревья:

1) с 6 ребрами и 3 висячими вершинами;

2) с 6 ребрами и 4 висячими вершинами;

3) с 7 ребрами и 3 висячими вершинами;

4) с 8 ребрами и 3 вершинами степени 3.

20. Используя теорему Кирхгофа о деревьях, найти число остовов у графов и (рис. 42).

Рис. 42

21. Найдите остовные деревья в графах .

22. Привести пример плоского графа, имеющего более двух граней, причем каждая грань пятиугольник (т.е. простой цикл длины 5).

23. Пусть – плоский кубический граф с 6 гранями. Найти число вершин и число ребер графа .

24. Пусть – плоский кубический граф, у которого граница каждой грани содержит не более 5 ребер. Доказать, что число ребер графа не превосходит 30.

25. Показать, что не существует плоского кубического графа, у которого граница каждой грани содержит не более 4 ребер, а общее число ребер превышает 12.

26. Существует ли простой планарный граф, у которого:

1) 7 вершин и 16 ребер;

2) 8 вершин и 17 ребер;

3) 6 вершин и 9 граней?

27. Какое наибольшее число граней может быть у плоского

5-вершинного графа, не имеющего петель и кратных ребер?

28. Построить все попарно неизоморфные простые плоские

6-вершинные графы, имеющие 8 граней.

29. Найти хроматические числа графов, изображенных на рис. 37–41.

30. Построить плоское корневое дерево по его коду :