2. На рисунке изображен граф. Определите: А) Вершины графа и их количество; Б) Ребра графа и их количество; В) Все пути из пункта А в пункт F, проходящие через пункт D; Г) Все циклы этого графа; Д) Степень каждой вершины и общую степень графа.

Решение:

А) Вершины графа: A, B, C, D, E, F, G. Их количество: 7.

Б) Ребра графа: (A, C), (A, B), (B, C), (B, D), (C, D), (C, E), (D, G), (E, F), (E, G). Их количество: 9.

В) Пути из А в F через D:

• A → B → D → E → F
• A → C → B → D → E → F
• A → C → D → E → F

Г) Циклы графа:

• B → C → D → B
• C → D → G → E → C
• B → D → G → E → C → B

Д) Степень каждой вершины и общую степень графа:

• Степень вершины A: 2
• Степень вершины B: 3
• Степень вершины C: 3
• Степень вершины D: 3
• Степень вершины E: 3
• Степень вершины F: 1
• Степень вершины G: 2

Общая степень графа = 2 + 3 + 3 + 3 + 3 + 1 + 2 = 17.