Степень вершины и анализ структуры графа

Зачем это в ЕГЭ.
В задании 1 ЕГЭ по информатике (1 первичный балл) проверяется умение применять свойства степеней вершин для анализа структуры графа. Требуется находить число рёбер, определять количество вершин заданной чётности или проверять условия существования эйлеровых путей/циклов. Этот подтип встречается в 65–75 % реальных вариантов ФИПИ последних лет.

Главная идея.
Ключ к решению — понять, что сумма степеней всех вершин всегда равна удвоенному числу рёбер (рукопожательная лемма). Это позволяет мгновенно восстанавливать недостающие данные о графе и анализировать его структуру: связность, наличие циклов, эйлеровы пути. Для ориентированных графов отдельно суммируются входящие и исходящие степени, которые всегда равны. Главное — сразу проверять чётность суммы и количество нечётных степеней.

Алгоритм (чеклист).
1. Определи тип графа (неориентированный или ориентированный) и выпиши степени всех вершин (отдельно in/out при необходимости).
2. Вычисли сумму степеней (или отдельно сумму in и out).
3. Примени формулу: для неориентированного графа $E = \frac{\sum \deg(v)}{2}$.
4. Проверь чётность суммы и неотрицательность степеней.
5. Если требуется анализ структуры — посчитай вершины с нечётной степенью и сравни с условиями эйлерова пути/цикла.
6. Запиши ответ и перепроверь арифметику.

Опоры (кратко).
- Рукопожательная лемма: $\sum_{v} \deg(v) = 2|E|$
- Число вершин нечётной степени всегда чётно.
- Эйлеров цикл: все $\deg(v)$ чётные.
- Эйлеров путь (не цикл): ровно две вершины нечётной степени.
- Для ориентированного графа: $\sum \deg^+(v) = \sum \deg^-(v) = |E|$

Пример 1 (неориентированный граф, подсчёт рёбер)
Задача. Неориентированный граф без петель имеет 6 вершин со степенями 3, 4, 2, 3, 2, 4. Определите количество рёбер в графе.

Шаг 1. Суммируем степени: $3 + 4 + 2 + 3 + 2 + 4 = 18$.
Шаг 2. По рукопожательной лемме $\sum \deg(v) = 2E$.
Шаг 3. $E = 18 / 2 = 9$.
Шаг 4. Проверка: сумма чётная, все степени от 2 до 4 (≤5), граф возможен.

Ответ: 9

Пример 2 (анализ структуры, эйлеров путь)
Задача. Неориентированный граф имеет 4 вершины A, B, C, D со степенями 2, 3, 3, 4.
а) Сколько рёбер в графе?
б) Существует ли в графе эйлеров путь?

Шаг 1. Суммируем степени: $2 + 3 + 3 + 4 = 12$.
Шаг 2. $E = 12 / 2 = 6$ (пункт а).
Шаг 3. Вершины нечётной степени: B (3) и C (3) — ровно две.
Шаг 4. По теореме эйлеров путь существует при ровно двух вершинах нечётной степени (пункт б).
Шаг 5. Проверка: сумма чётная, для цикла нечётных должно быть 0 — здесь путь, но не цикл.

Ответ: а) 6; б) да, существует эйлеров путь.

Типичные ошибки.
1. Делят сумму степеней на 1 вместо 2. — Получают в два раза больше рёбер, полностью игнорируя рукопожательную лемму.
2. Не проверяют чётность суммы перед ответом. — Указывают число рёбер для несуществующего графа, хотя сумма нечётная.
3. Путают условие эйлерова пути и цикла. — Думают, что для пути нужны все чётные степени, хотя достаточно ровно двух нечётных.
4. В ориентированном графе суммируют только исходящие степени. — Забывают, что суммы in и out обязаны совпадать.
5. Считают степень вершины без учёта, что в неориентированном графе каждая дуга даёт +1 обеим вершинам. — Ошибаются при ручном пересчёте по списку рёбер.

Дальше.
Переходи к матрице смежности и алгоритмам поиска путей в графе для задач 23–24 ЕГЭ.