Эйлеров путь
англ. Eulerian path
Маршрут по графу, проходящий по каждому ребру ровно один раз; существует тогда и только тогда, когда число вершин нечётной степени равно 0 или 2.
Представьте: нужно обойти город, пройдя по каждому мосту ровно один раз. Именно эта задача про кёнигсбергские мосты в 1736 году запустила теорию графов. Эйлеров путь — маршрут, который проходит по каждому ребру графа ровно один раз (разрешается повторять вершины, но не рёбра). Если маршрут замыкается в стартовой вершине, его называют эйлеровым циклом, а граф — эйлеровым.
Критерий красив до неприличия. Эйлеров цикл существует ⟺ граф связный и ВСЕ вершины имеют чётную степень. Эйлеров путь (не цикл) ⟺ связность и ровно ДВЕ вершины нечётной степени — они и будут началом и концом маршрута. Интуиция: заходя в промежуточную вершину, мы обязаны из неё выйти, — пары рёбер, отсюда чётность; нечётными могут быть только крайние точки маршрута. В Кёнигсберге все четыре берега имели нечётные степени (3, 3, 3, 5) — поэтому Эйлер и заключил, что обход невозможен.
Где это применяется: рисование фигур одним росчерком пера, задачи о маршрутах уборочной техники и снегоуборщиков (каждое ребро сети = отрезок улицы), тестирование печатных плат (каждую дорожку проверим один раз), биоинформатика (сборка генома по перекрывающимся чтениям — там эйлеров путь по графу перекрытий). Если хотите пощупать графы руками — откройте интерактивные графы и обходы графов, базовые факты собраны в справочнике по графам, а термин граф поможет, если вы только начинаете.
Частые вопросы
Чем эйлеров путь отличается от эйлерова цикла?
Цикл замкнут: старт и финиш совпадают, и для него нужны ВСЕ степени чётными. Путь — незамкнутый маршрут: он существует, если нечётных вершин ровно две (из одной стартуем, в другой заканчиваем). Каждый эйлеров цикл автоматически даёт путь, но не наоборот.
Всегда ли можно проверить существование пути без поиска?
Да — в этом прелесть критерия: посчитайте степени всех вершин. Связный граф с 0 или 2 нечётными вершинами гарантированно имеет эйлеров маршрут. Никакого перебора маршрутов не нужно: чётность решает всё.
Что делать, если нечётных вершин больше двух?
Эйлерова маршрута нет. Но можно минимизировать повторения: задача «пройти все рёбра, повторяя как можно меньше» — это задача китайского почтальона, она решается добавлением рёбер-дубликатов между нечётными вершинами через паросочетание минимального веса.