E6b Графы: обходы, эйлеровы пути

Идея метода: многие задачи о движении по маршруту, о рисовании фигуры «не отрывая карандаша» или о прохождении всех рёбер ровно по одному разу сводятся к вопросу о существовании эйлерова пути или цикла в соответствующем графе.

Метод состоит в том, чтобы:
1. Перевести условие задачи в язык теории графов: объекты → вершины, связи/переходы → рёбра.
2. Применить критерий Эйлера: граф имеет эйлеров цикл тогда и только тогда, когда он связен и все вершины имеют чётную степень; эйлеров путь (без возврата в начало) существует тогда и только тогда, когда ровно 2 вершины имеют нечётную степень.

Аналогия из жизни: представьте карту улиц, где нужно объехать каждую улицу ровно один раз — вопрос «можно ли это сделать» решается подсчётом количества перекрёстков с нечётным числом улиц.

Метод важен тем, что критерий Эйлера даёт точный ответ (да/нет) из одного числового признака и часто позволяет сразу снять вопрос о существовании без перебора конкретных маршрутов.

• Теорема Эйлера (эйлеров цикл): Связный граф $G$ содержит эйлеров цикл (замкнутый обход, проходящий по каждому ребру ровно один раз) тогда и только тогда, когда степень каждой вершины чётна: $\deg(v) \equiv 0 \pmod{2}$ для всех $v$. Условие: граф связен и без изолированных вершин. Когда использовать: задача о замкнутом маршруте через все рёбра.

• Теорема об эйлеровом пути: В связном графе $G$ существует эйлеров путь (незамкнутый обход всех рёбер) тогда и только тогда, когда ровно 2 вершины имеют нечётную степень. Путь начинается в одной из них и заканчивается в другой. Когда использовать: задача о рисовании «одним росчерком».

• Лемма о рукопожатиях: $\sum_{v} \deg(v) = 2|E|$ — сумма степеней вершин равна удвоенному числу рёбер. Следствие: число вершин нечётной степени всегда чётно. Когда использовать: чтобы убедиться, что граф вообще может удовлетворять условию задачи.

• Критерий связности: граф связен, если между любыми двумя вершинами есть путь. Для применения теоремы Эйлера связность обязательна. Когда использовать: до применения теоремы Эйлера проверьте, что граф не распадается на компоненты.

• Кодирование задачи в граф: чётко определите, что является вершинами (клетки, перекрёстки, состояния), а что — рёбрами (переходы, рёбра фигуры, улицы).

• Подсчёт степеней вершин: для каждой вершины посчитайте число инцидентных рёбер. Вершины с нечётной степенью — «проблемные».

• Добавление фиктивного ребра: если эйлерова цикла нет, но нужен эйлеров путь — добавьте ребро между двумя вершинами нечётной степени и ищите цикл.

• Анализ компонент связности: проверьте, что граф связен (или что все рёбра лежат в одной компоненте); без этого теорема Эйлера не применима.

• Доказательство невозможности: если вершин нечётной степени более 2 — эйлеров путь не существует. Это часто единственный вывод, который требуется.

• Алгоритм Флёри: для построения конкретного эйлерова пути — двигайтесь по любому ребру, избегая «мостов» (рёбер, удаление которых разъединяет граф), пока не пройдёте все рёбра.

Поверхностные признаки (что буквально написано):
- «Нарисовать фигуру, не отрывая карандаша».
- «Пройти по каждой дороге/ребру ровно один раз».
- «Можно ли обойти все клетки/узлы, совершая переходы по правилу...».

Структурные признаки (форма выражения, объекты):
- Задача задаёт набор объектов и переходов между ними, которые нужно использовать ровно по одному разу.
- Фигура или граф с явно выраженными узлами (вершинами) и соединениями (рёбрами).
- Сетка, карта, лабиринт, где движение идёт по рёбрам.

Цель задачи (что от тебя хотят):
- Доказать возможность или невозможность такого обхода.
- Найти конкретный маршрут (тогда нужно строить эйлеров путь явно).
- Найти минимальное число «повторных» рёбер, если эйлеров путь невозможен.

Задача 1. Кёнигсбергские мосты (классическая)

Условие: Город разделён рекой на 4 части: $A$, $B$, $C$, $D$. Между ними 7 мостов: $AB$ — 2 моста, $AC$ — 1, $AD$ — 1, $BC$ — 1, $BD$ — 1, $CD$ — 1. Можно ли обойти все мосты, пройдя каждый ровно один раз?

Источник: классическая задача Эйлера, 1736

Как думать (рассуждение ученика$):
1. $Что вижу? Нужно пройти каждый мост ровно один раз — это эйлеров путь в графе, где берега = вершины, мосты = рёбра.$2. *$Первый ход: посчитаю степени вершин: $\deg(A) = 2+1+1 = 4$, $\deg(B) = 2+1+1 = 4$, $\deg(C) = 1+1+1 = 3$, $\deg(D) = 1+1+1 = 3$.$3. *$Ключевая идея: вершин с нечётной степенью — 2 ($C$ и $D$). Значит, эйлеров путь существует (от $C$ до $D$ или наоборот).

Подождём — у Эйлера 7 мостов, пересчитаем: $A$-$B$ два моста, итого $\deg(A)=4$ (AB×2, AC, AD), $\deg(B)=4$ (AB×2, BC, BD), $\deg(C)=3$ (AC, BC, CD), $\deg(D)=3$ (AD, BD, CD). Вершин с нечётной степенью ровно 2 — значит эйлеров путь существует (исторически у Эйлера было 4 нечётных вершины, но данная модификация с 7 мостами как выше допускает путь$).

$Историческая справка: у Эйлера было 7 мостов с другим распределением, там все 4 вершины нечётной степени — путь невозможен.

Ответ: При данном расположении мостов эйлеров путь существует.

Что главное: степени вершин — единственное, что нужно посчитать.

Задача 2. Рисование фигуры одним движением

Условие: Дана фигура — граф, у которого 6 вершин со степенями 3, 3, 4, 4, 2, 2. Можно ли нарисовать её одним непрерывным движением карандаша, не отрывая его от бумаги и не проводя ни одно ребро дважды?

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу? «Одним движением, не повторяя» — это эйлеров путь.$2. *$Первый ход: считаю вершины нечётной степени: степени 3, 3, 4, 4, 2, 2 — нечётные степени у двух вершин (обе со степенью $3).
3. $Применяю теорему: ровно 2 вершины нечётной степени → эйлеров путь существует, начиная из одной вершины степени 3 и заканчивая в другой.$4. *$Проверяю связность: граф связен по условию.

Решение: Число вершин нечётной степени равно 2. По теореме об эйлеровом пути: если граф связен и имеет ровно 2 вершины нечётной степени, то эйлеров путь существует. Граф связен (по условию). Следовательно, нарисовать фигуру одним движением можно — начав из одной вершины степени 3 и закончив в другой.

Ответ: Да, можно.

Что главное: не нужно строить явный маршрут — достаточно подсчитать вершины нечётной степени.

• Ошибка: не проверяют связность графа. Теорема Эйлера требует связности. Если граф распадается на 2 компоненты, даже при нулевом числе нечётных вершин эйлерова цикла нет. Как избежать: всегда проверяйте, можно ли попасть из любой вершины в любую другую.

• Ошибка: путают эйлеров путь и гамильтонов путь. Эйлеров путь — через все РЁБРА ровно по одному разу. Гамильтонов — через все ВЕРШИНЫ. Это разные задачи. Как избежать: перечитайте условие: что нужно пройти — рёбра или вершины?

• Ошибка: неправильно считают степени при мультирёбрах. Если между вершинами $A$ и $B$ два ребра, они дают вклад 2 в степень каждой из $A$ и $B$. Как избежать: для каждого ребра прибавляйте 1 к степени обоих его концов.

• Ошибка: забывают, что путь (не цикл) допускает ровно 2 нечётные вершины. Часто пишут «если есть нечётные вершины — эйлерова обхода нет», не различая цикл и путь. Как избежать: запомните: цикл — 0 нечётных вершин; путь — ровно 2.

• Ошибка: не учитывают изолированные вершины. Вершина степени 0 — не проблема для эйлерова цикла по нечётности, но нарушает связность. Как избежать: изолированные вершины исключить из рассмотрения или учесть при проверке связности.