Задачи для самостоятельного решения
№ 2.1 Показать, что два графа на рис. 2.6 изоморфны.
Рис. 2.6
№ 2.2 «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца.
Можно ли провести непересекающиеся дорожки от каждого дома к колодцу?№ 2.3 Найти степени и числа вершин для графов пяти правильных многогранников.
№ 2.4 Для графов, изображенных на рис. 2.7, указать пары, изоморфные друг другу.
А Б В
 |
Г Д Е
Ж З И
Ж З И
 |
К Л М
Рис.2.7
№ 2.5 Среди графов, указанных на рис. 2.8, выделить полные графы (без учета петель).
А Б В Г
Д Е Ж
И К Л М
Рис. 2.8
№ 2.6 Дан граф G (Рис. 2.9). Указать, какие из графов, изображенных на рис. 2.9б, являются частями графа G и какие – подграфами.
 |
Рис. 2.9
А Б В
Г Д Е
Ж З И
К Л М Н
Рис. 2.9б.
№ 2.8 Какие из графов, приведенных на рис.2.8 и 2.9, являются плоскими?
№ 2.9.
Составить матрицы смежности и инцидентности для правильных многогранников.№ 2.10. Построить матрицы смежности графов, изображенных на рис. 2.9.
№ 2.11 Для заданного на рис. 2.10 (а¸к) графа построить: матрицу смежности, матрицу инциденции, матрицу достижимостей. Найти число внутренней устойчивости. Найти число внешней устойчивости.
А Б В
Г Д Е Ж
З И К
Рис. 2.10.
 |
№ 2.12. Для приведенных на рис. 2.11. графов G1 и G2 найти 
, 
, 
.
А Б
В Г
Д Е
Ж З
Рис. 2.11
№ 2.13. Построить графы, матрицы смежности которых указаны:
№ 2.14. Построить графы, матрицы инцидентности которых указаны:
;
№ 2.15 Груз доставляется из пункта Х0 в пункт Х7 через перевалочные пункты Х0…Х7 (Рис.2.12). Расстояния между пунктами ХiXj указаны на соответствующем графе. Найти путь минимальной длины между Х0 и Х7 и его длину.
А Б
В Г
Рис. 2.12
№ 2.16 Задан сетевой граф проекта (Рис.2.12). Найти критический путь и минимальное время проекта