Эйлеровы и Гамильтоновы графы: Задачи маршрутизации

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

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

Гамильтонов путь, названный в честь ирландского математика Уильяма Роуэна Гамильтона (изобретателя игры "Икосиан"), — это маршрут, проходящий через каждую вершину графа ровно один раз. Соответственно, гамильтонов цикл возвращается в исходную вершину. В отличие от эйлеровых графов, для гамильтоновых не существует простых, универсальных и необходимых критериев проверки. Существуют лишь достаточные условия: например, теорема Дирака гласит, что если в графе с n > 2 вершинами степень каждой вершины не меньше n/2, то граф гамильтонов.

Задача поиска гамильтонова цикла относится к классу NP-полных, что означает отсутствие известного полиномиального алгоритма для ее решения на больших графах. Классический пример ее проявления — знаменитая задача коммивояжера (TSP), где требуется найти кратчайший гамильтонов цикл во взвешенном графе. Эта задача повсеместно применяется в логистике, разводке печатных плат, проектировании микросхем и планировании расписаний. Для решения TSP на практике программисты вынуждены применять эвристические алгоритмы, генетические алгоритмы и методы ветвей и границ, так как полный перебор вариантов (число которых растет как факториал от количества вершин) занимает непозволительно много времени даже на суперкомпьютерах.