1. Представить граф ( рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.
2. Составить матрицу инцидентичности для мультиграфа, изображенного на рис 4.51.
3. Найти все неизоморфные подграфы и части графа K3.
4. Представить в геометрической и матричной формах графы (рис. 4.52)
5. Для графов G1 и G2 из предыдущей задачи найти
6. C помощью матрицы смежности графа ( рис. 4.53) найти его матрицы достижимости, контрдостижимости и сильных компонент.
7. Найти матрицу расстояний, диаметр, радиус, центральные и переферийные вершины графа, изображенного на рис. 4.54.
8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа ( рис. 4.55).
9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.
10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей: а) графа K5; б) графа, изображенного на рис. 4.56.
11. Построить все неизоморфные трех-,четырех- и пятивершинные деревья.
12. Найти остов минимального веса взвешенного графа ( рис. 4.57).
13. Найти упорядоченный лес, соответствующий бинарному дереву, изображенному на рис. 4.58.
14. Найти матрицы фундаментальных циклов и фундаментальных разрезов графа ( рис. 4.59).
15. Найти хроматическое число графа ( рис. 4.60).
16. Найти толщину графа. ( рис. 4.61).