Задание 3. На рисунке изображён граф. а) Найдите степень вершины С? б) Сколько в этом графе вершин четной степени? в) Сколько вершин в этом графе имеют наименьшую степень?

Решение:

Степень вершины — это количество ребер, исходящих из этой вершины.

• а) Степень вершины C: Вершина C соединена с вершинами D, B и F. Следовательно, степень вершины C равна 3.
• б) Количество вершин четной степени:
  • Степень A = 2 (соединена с F, H)
  • Степень B = 2 (соединена с C, D)
  • Степень C = 3 (соединена с D, B, F)
  • Степень D = 3 (соединена с C, B, G)
  • Степень F = 3 (соединена с A, C, H)
  • Степень G = 1 (соединена с D)
  • Степень H = 2 (соединена с A, F)
  Вершины с четной степенью: A (2), B (2), H (2). Всего 3 вершины.
• в) Количество вершин с наименьшей степенью: Наименьшая степень в данном графе — 1, и она принадлежит вершине G. Таких вершин — 1.

Ответ:

• а) 3
• б) 3
• в) 1