Решение задачи по графам: Вариант 1

Задания для письменного выполнения Сведения о графах (повторение) 1 вариант Задание 1. а) У данного графа 8 вершин (считая изолированную точку в центре). б) Степени вершин (количество выходящих линий): Верхняя левая: 5 Нижняя левая: 2 Изолированная (в центре): 0 Нижняя центральная: 4 Верхняя правая: 5 Крайняя правая: 4 Две вершины, образующие петли и кратные ребра, имеют соответствующие степени согласно количеству инцидентных ребер. в) Количество ребер: 10. г) Кратных ребер: 2 пары (между верхней левой и нижней центральной вершинами). д) Петель в графе: 2 (у верхней правой и крайней правой вершин). Задание 2. Для решения воспользуемся леммой о рукопожатиях: сумма степеней всех вершин графа равна удвоенному количеству его ребер. \[ \sum deg(v) = 2 \cdot E \] 1) Найдем сумму степеней: \[ 3 + 5 + 4 + 2 + 4 = 18 \] 2) Найдем количество ребер: \[ E = 18 : 2 = 9 \] Ответ: в графе 9 рёбер. Задание 3. а) Существует ли граф, в котором сумма степеней всех вершин равна 463? Ответ: Нет, не существует. Обоснование: Согласно лемме о рукопожатиях, сумма степеней вершин всегда должна быть четным числом, так как она равна \( 2 \cdot E \). Число 463 — нечетное. б) Сумма степеней равна 294. Сколько в графе рёбер? Решение: \[ E = 294 : 2 = 147 \] Ответ: 147 рёбер. Задание 4. Чтобы граф можно было нарисовать не отрывая карандаша (эйлеров путь), он должен быть связным и иметь не более двух нечетных вершин. Посчитаем степени вершин на рисунке: \( deg(A) = 3 \) (нечетная) \( deg(B) = 4 \) (четная) \( deg(C) = 3 \) (нечетная) \( deg(D) = 2 \) (четная) \( deg(E) = 2 \) (четная) \( deg(F) = 4 \) (четная) \( deg(G) = 3 \) (нечетная) \( deg(H) = 3 \) (нечетная) Итого имеем 4 нечетные вершины (A, C, G, H). Ответ: Нет, нельзя. Обоснование: Граф имеет более двух вершин с нечетной степенью (их 4), следовательно, в нем нет эйлерова пути.