Задание 1. На рисунке изображен граф. а) Найдите степень каждой его вершины. б) Можно ли обвести этот граф карандашом, не отрывая карандаша от бумаги и не проводя одну линию дважды (одним росчерком). в) Найдите суммарную степень вершин этого графа.

Задание 1.

На рисунке изображен граф с вершинами A, B, C, D, E, F, G, H.

1. Степень вершин:
• Степень вершины — это количество ребер, которые к ней присоединены.
• A: 3 (соединена с B, C, G)
• B: 3 (соединена с A, D, E)
• C: 2 (соединена с A, F)
• D: 2 (соединена с B, H)
• E: 3 (соединена с B, F, G)
• F: 3 (соединена с C, E, G)
• G: 3 (соединена с A, E, F)
• H: 1 (соединена с D)
2. Можно ли обвести граф одним росчерком?
• Чтобы граф можно было обвести одним росчерком (то есть пройти по всем ребрам ровно один раз, не отрывая карандаша), он должен иметь либо 0, либо 2 вершины с нечетной степенью.
• В нашем графе степени вершин: A(3), B(3), C(2), D(2), E(3), F(3), G(3), H(1).
• Вершины с нечетной степенью: A, B, E, F, G, H. Всего 6 вершин с нечетной степенью.
• Поскольку вершин с нечетной степенью больше двух, этот граф нельзя обвести одним росчерком.
3. Суммарная степень вершин:
• Сумма степеней всех вершин графа равна удвоенному количеству ребер.
• Сумма степеней = 3 + 3 + 2 + 2 + 3 + 3 + 3 + 1 = 20.
• Количество ребер = 10. (AB, AC, AG, BD, BE, CF, CE, EF, EG, DH).
• Проверка: 20 = 2 * 10.

Ответ:

а) Степени вершин: A-3, B-3, C-2, D-2, E-3, F-3, G-3, H-1.

б) Нет, нельзя, так как 6 вершин имеют нечетную степень.

в) Суммарная степень вершин равна 20.