Вероятность и статистика · Графы и деревья

Эйлеров обход

Когда можно пройти каждое ребро ровно один раз и как степени задают начало и конец.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

Критерий быстро решает задачи об обходе дорог, мостов и линий без повторения. Он отделяет задачу о рёбрах от гамильтоновой задачи, где по одному разу посещают вершины.

Главная идея. Эйлерова цепь проходит каждое ребро графа ровно один раз, хотя вершины могут повторяться. В связной части с рёбрами такой маршрут существует только при нуле или двух вершинах нечётной степени.

План рассуждения и проверка понимания

Игнорируйте изолированные вершины и проверьте, что все вершины ненулевой степени находятся в одной компоненте связности.
Посчитайте степень каждой вершины, учитывая каждое ребро у обоих его концов, и найдите нечётные степени.
При нуле нечётных вершин ищите замкнутый цикл, при двух начинайте в одной нечётной и заканчивайте в другой.
Если нечётных вершин больше двух или рёберные компоненты раздельны, объясните, почему общего эйлерова обхода нет.

Частая ошибка. Проверить только чётность степеней и объявить два несвязанных треугольника эйлеровым графом, хотя между их рёбрами невозможно перейти.

Как проверить себя. К критерию степеней обязательно добавьте связность всех вершин с ненулевой степенью; отдельные рёберные компоненты требуют разных маршрутов.

Схема к теме

Наглядная модель: Эйлеров обход

Когда можно пройти каждое ребро ровно один раз и как степени задают начало и конец.

Эйлеров обход → Эйлер
Эйлеров обход → обход рёбер
Эйлеров обход → нечётная степень

Схема связывает понятие «Эйлеров обход» с его ключевыми признаками. Вывод: Свяжите определение, условия и обозначения: тогда формула станет краткой записью уже понятной идеи.

Проверка пониманияОбъясните тему своими словами

Сравните треугольник, цепочку A–B–C–D и звезду с тремя листьями по числу нечётных вершин и типу возможного обхода.

В хорошем объяснении есть:

У треугольника ноль нечётных вершин и есть замкнутый цикл; у цепочки две и есть открытая цепь.
У звезды четыре нечётные вершины, поэтому пройти каждое ребро ровно один раз невозможно.

Пройти все рёбра по одному разу

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

Рассмотрим конечный неориентированный граф с хотя бы одним ребром. Все вершины ненулевой степени должны лежать в одной компоненте: между раздельными частями невозможно перейти, не используя отсутствующее ребро.

Критерий существования

Если все степени чётные, существует замкнутый эйлеров обход. Если нечётных вершин ровно две, существует незамкнутая эйлерова цепь, начинающаяся в одной из них и заканчивающаяся в другой. При большем числе нечётных вершин такого обхода нет.

Необходимость понятна по входам и выходам: каждое посещение внутренней вершины расходует пару рёбер. Непарные концы возможны только в начале и конце. Достаточность доказывают построением замкнутых фрагментов и их объединением; одна проверка чётности без связности недостаточна.

Три примера

Треугольник имеет степени 2, 2, 2. Обход $A-B-C-A$ проходит каждое ребро один раз и возвращается к началу.
Цепочка $A-B-C-D$ имеет нечётные вершины $A,D$ . Эйлеров обход начинается на одном конце и заканчивается на другом.
Звезда с тремя листьями имеет степени 3, 1, 1, 1. Нечётных вершин четыре, поэтому пройти все рёбра ровно один раз нельзя.

Ошибки

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

Формула, смысл и ограничения

Главные формулы с расшифровкой

\#\{v:\deg(v)\text{ нечётна}\}\in\{0,2\}

Формула словами: Критерий эйлеровой цепи в неориентированном графе при связности всех вершин ненулевой степени.

От простого к сложному

Проверьте себя

Сначала запишите решение самостоятельно. Затем можно открыть намёк, сравнить каждый переход с пошаговым разбором и только после этого посмотреть ответ. Прогресс сохраняется в этом браузере.

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.