Задачи и упражнения. 1. Доказать, что в неорграфе число вершин с нечетной степенью четно.

1. Доказать, что в неорграфе число вершин с нечетной степенью четно.

2. Построить граф (если он существует) с последовательностью степеней

а) (4,3,3,2,2);

б) (5,4,2,2,1) .

3. Найти матрицы достижимости и контрдостижимости для графов G₁ ,G₂, G₄, изображенных на рис. 4.57.

Рис. 4.57

4. Доказать, что если в n-вершинном графе степень каждой вершины не меньше, чем (n-1)/2 , то он связен.

5. Доказать, что если G - несвязный граф, то `G - связный.

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

7. Для графов, изображенных на рис. 4.58, найти сильнее компоненты, построить конденсацию, найти базы и антибазы.

Рис. 4.58

8. Доказать, что хроматическое число каждого n-вершинного дерева (n³2) равно 2.

9. Построить остовы для графов, изображенных на рис. 4.59.

Рис. 4.59

10. Существует ли эйлеров цикл в графах, изображенных на рис. 4.60 ?

Рис. 4.60

11. Определить, какие из графов пяти правильных многогранников имеют эйлеровы циклы.

12. Составить алгоритм, основанный на алгоритме Флери и позволяющий найти все эйлеровы циклы графа.

13. Определить гамильтоновы пути и контуры методом перебора Робертса и Флореса в графах, изображенных на рис. 4.61.

Рис. 4.61

14. Для графа построить, если это возможно, его уклад­ку на плоскости.

а) б)

д) е)