В графе 14 рёбер. Каждая вершина графа имеет или степень 2, или степень 5. Причём вершин степени 2 столько же, сколько вершин степени 5. Сколько вершин в этом графе?
Показать решение
Пусть вершин степени 2 столько же, сколько вершин степени 5 — по штук. Тогда вершин всего .
Сумма степеней равна удвоенному числу рёбер:
Ответ: .
Теория
1) Сумма степеней всегда чётна (так как равна 2E)
Число вершин нечётной степени всегда чётно
Если при решении получается нецелое число рёбер — граф не существует
2) Проверка существования графа:
Сумма степеней должна быть чётным числом
Каждая степень должна быть неотрицательным целым числом
Максимальная степень вершины в простом графе с n вершинами: deg(v) ≤ n-1
3) Алгоритм решения:
- Найти сумму степеней всех вершин
- Разделить на 2
- Проверить, что результат — целое число
- Если да — это количество рёбер, если нет — граф не существует