Задачи и упражнения. 2. Составить матрицу инцидентичности для мультиграфа, изображенного на рис 4.51.

1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.

2. Составить матрицу инцидентичности для мультиграфа, изображенного на рис 4.51.

3. Найти все неизоморфные подграфы и части графа K₃.

4. Представить в геометрической и матричной формах графы (рис. 4.52)

5. Для графов G₁ и G₂ из предыдущей задачи найти

6. C помощью матрицы смежности графа (рис. 4.53) найти его матрицы достижимости, контрдостижимости и сильных компонент.

7. Найти матрицу расстояний, диаметр, радиус, центральные и переферийные вершины графа, изображенного на рис. 4.54.

8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. 4.55).

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

10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей: а) графа K₅; б) графа, изображенного на рис. 4.56.

11. Построить все неизоморфные трех-,четырех- и пятивершинные деревья.

12. Найти остов минимального веса взвешенного графа (рис. 4.57).

13. Найти упорядоченный лес, соответствующий бинарному дереву, изображенному на рис. 4.58.

14. Найти матрицы фундаментальных циклов и фундаментальных разрезов графа (рис. 4.59).

15. Найти хроматическое число графа (рис. 4.60).

16. Найти толщину графа. (рис. 4.61).