Эйлеров цикл

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

История

Задача о кёнигсбергских мостах

В 1736 году Леонард Эйлер опубликовал работу «Solutio problematis ad geometriam situs pertinentis» (Решение задачи, относящейся к геометрии положения), в которой рассмотрел задачу: можно ли, начав с одной из четырёх частей города Кёнигсберг (ныне Калининград), пройти по каждому из семи мостов ровно один раз и вернуться в исходную точку. Эйлер представил схему города в виде графа, где вершины обозначали участки суши, а рёбра — мосты. Он доказал, что такой маршрут невозможен, поскольку в графе было четыре вершины нечётной степени. Это исследование считается первым в истории теории графов.

Развитие теории

В XIX веке понятие эйлерова цикла было формализовано. В 1873 году немецкий математик Карл Хирхольцер опубликовал алгоритм нахождения эйлерова цикла в неориентированном графе. В XX веке теория эйлеровых графов получила развитие в работах Ойстена Оре, Клода Бержа и других математиков. Эйлеровы циклы стали применяться в задачах оптимизации маршрутов, проектирования сетей и биоинформатики.

Определения и свойства

Основные понятия

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

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

Для существования эйлерова цикла в неориентированном графе необходимо и достаточно, чтобы:

1. Граф был связным (за исключением изолированных вершин).
2. Все вершины имели чётную степень.

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

Следствия

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

Алгоритмы нахождения

Алгоритм Хирхольцера

Один из наиболее эффективных алгоритмов нахождения эйлерова цикла в неориентированном графе. Работает за время O(E), где E — количество рёбер.

1. Проверить, что граф эйлеров (связен и все вершины имеют чётную степень).
2. Выбрать произвольную начальную вершину.
3. Строить цикл, проходя по рёбрам, удаляя их из графа, пока не вернёмся в начальную вершину.
4. Если остались непройденные рёбра, найти вершину в текущем цикле, у которой есть непройденные рёбра, и повторить шаг 3, вставляя новый цикл в текущий.
5. Объединить все циклы в один.

Алгоритм Флёри

Более простой, но менее эффективный (O(E²)) алгоритм. Основан на правиле: не использовать мост (ребро, удаление которого разрывает граф), если есть альтернатива. Применяется в учебных целях.

Применение

Транспортные задачи

Эйлеровы циклы используются для оптимизации маршрутов уборки улиц, почтовой доставки, инспекции дорог и линий электропередач. Например, задача китайского почтальона (Chinese Postman Problem) сводится к нахождению кратчайшего замкнутого маршрута, покрывающего все рёбра графа, что требует добавления рёбер для получения эйлерова графа.

Биоинформатика

В секвенировании ДНК эйлеровы циклы применяются для сборки генома из коротких фрагментов (метод de Bruijn graph). Граф де Брёйна строится так, что его эйлеров путь соответствует последовательности нуклеотидов.

Проектирование сетей

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

Криптография

Эйлеровы циклы применяются в некоторых схемах шифрования и генерации псевдослучайных последовательностей.

Примеры

Пример 1: Граф-звезда

Рассмотрим граф с тремя вершинами, соединёнными в виде треугольника (цикл из трёх рёбер). Каждая вершина имеет степень 2 (чётная), граф связен. Эйлеров цикл: A-B-C-A.

Пример 2: Граф с двумя вершинами нечётной степени

Граф в виде буквы «П»: вершины A, B, C, D, рёбра AB, BC, CD, DA, AC. Степени: A=3, B=2, C=3, D=2. Две вершины нечётной степени — существует эйлеров путь, начинающийся в A и заканчивающийся в C (или наоборот), но не цикл.

Пример 3: Граф с четырьмя вершинами нечётной степени

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

Интересные факты

• Леонард Эйлер решил задачу о кёнигсбергских мостах в возрасте 29 лет, находясь в Санкт-Петербурге, где работал в Петербургской академии наук.
• В современном Калининграде сохранилось лишь пять из семи исторических мостов, но задача по-прежнему не имеет решения из-за нечётных степеней вершин.
• Эйлеровы циклы используются в головоломках, таких как «Рисование одной линией» (Unicursal drawing).
• Понятие эйлерова цикла обобщается на мультиграфы (графы с кратными рёбрами) и псевдографы (с петлями).

Критика и ограничения

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

Источники

• Эйлер Л. «Solutio problematis ad geometriam situs pertinentis» (1736).
• Хирхольцер К. «Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren» (1873).
• Оре О. «Теория графов» (1962).
• Берж К. «Теория графов и её применения» (1958).
• Уилсон Р. «Введение в теорию графов» (1972).