Эйлеров маршрут: каждое ребро ровно один раз

Проверить степени и связность непустой части простого неориентированного графа и построить полный маршрут по всем рёбрам.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

1 → 2 → 3 → 1

  1. Условия существования проверены.
  2. Каждое неориентированное ребро удалено с обеих сторон при использовании.

Метод и условия расчёта

В связной непустой части допускаются ноль или две вершины нечётной степени.

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

Теория к методу

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

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

Пример: Соединим квадрат 1–2–3–4–1 с треугольником 2–5–6–2. У общей вершины 2 степень четыре, у остальных два. Подходящий маршрут: 1→2→5→6→2→3→4→1.

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

Вопросы по теме

Изолированная вершина мешает маршруту по рёбрам?

Нет, если все непустые рёбра лежат в одной компоненте.

Это путь без повторения вершин?

Нет. Повторяться могут вершины; каждое ребро используется ровно один раз.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.