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