2015-05-20
4944
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. Построить плоское корневое дерево по его коду 
:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
.
31. По вектору установить, является ли он кодом какого-либо дерева:
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
.
32. Построить коды деревьев, изображенных на рис. 43.
Рис. 43
33. Пусть корневое дерево имеет 
висячих вершин и не имеет вершин степени 2, отличных от корня. Доказать, что общее число вершин не превосходит 
.
