Эйлеров маршрут: каждое ребро ровно один раз
Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.
Ваш пример
Разбор примера
1 → 2 → 3 → 1
- Условия существования проверены.
- Каждое неориентированное ребро удалено с обеих сторон при использовании.
Метод и условия расчёта
В связной непустой части допускаются ноль или две вершины нечётной степени.
Стековый обход удаляет использованные рёбра; число записей вершин на единицу больше числа рёбер.
Теория к методу
В эйлеровом маршруте ограничено повторение рёбер, а не вершин. Сначала проверяют связность части графа с рёбрами и число нечётных степеней. Затем строят маршрут, сохраняя возможность вернуться к ранее встреченной вершине через другие ещё не использованные рёбра.
Посчитайте степени всех вершин. Для замкнутого обхода они должны быть чётными: каждое прибытие сопоставляется с уходом. Для незамкнутого маршрута допускаются ровно две нечётные вершины, которые станут концами. Эти условия относятся к неориентированным рёбрам. Переносить их на ориентированную сеть без изменения баланса входов и выходов нельзя.
Пример: Соединим квадрат 1–2–3–4–1 с треугольником 2–5–6–2. У общей вершины 2 степень четыре, у остальных два. Подходящий маршрут: 1→2→5→6→2→3→4→1.
Семь исходных рёбер дают восемь позиций маршрута. Встроенный треугольный фрагмент возвращается в общую вершину и позволяет затем закончить квадрат. Подсчёт каждого неориентированного ребра подтверждает, что повтора или пропуска нет.
Вопросы по теме
Изолированная вершина мешает маршруту по рёбрам?
Нет, если все непустые рёбра лежат в одной компоненте.
Это путь без повторения вершин?
Нет. Повторяться могут вершины; каждое ребро используется ровно один раз.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.