Эйлеров цикл

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

Интуиция — рисунок одним росчерком. Обводим фигуру, не отрывая карандаш: рёбра — линии, вершины — узлы; рука вернулась в старт — цикл. Родоначальница всей темы — задача о кёнигсбергских мостах (Эйлер, 1736): четыре части города, семь мостов, обойти все мосты по разу невозможно. Отличие от гамильтонова цикла принципиально: эйлеров проходит все рёбра по разу, гамильтонов — все вершины по разу. Проверка эйлеровости — мгновенный подсчёт степеней; существование гамильтонова цикла — NP-полная задача без простого критерия.

Микропример — Кёнигсберг: четыре части суши, семь мостов; степени вершин $5,3,3,3$. Сумма $5+3+3+3=14=2\cdot 7$ сходится с числом мостов, но нечётных вершин четыре — ни цикла, ни даже пути (для пути нужны ровно две нечётные). Контраст на малых графах: квадрат с диагональю — степени $3,3,2,2$: ровно две нечётные, эйлеров путь есть (из одной нечётной вершины в другую), цикла нет. Квадрат без диагонали — степени $2,2,2,2$: цикл есть, обходим четыре стороны и замыкаемся. Строить маршрут умеет алгоритм Хирхольцера: идём по неиспользованным рёбрам, а найденные циклы вставляем в общий маршрут.

Обходы и все критерии — урок обходы графов, базовая терминология — урок основы графов. Словарь: лемма о рукопожатии — почему сумма степеней равна $2|E|$; эйлеров путь — открытый маршрут с двумя нечётными вершинами. Потренироваться на степенях и чётности — тренажёр по графам, формулы — в шпаргалке по графам.