🔀 Дискретка

Гамильтонов цикл

англ. Hamiltonian cycle

Цикл, проходящий через каждую вершину графа ровно один раз и возвращающийся в стартовую; проверка существования — NP-полная задача без простого критерия.

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

Вопрос «есть ли гамильтонов цикл» NP-полен: полиномиального критерия не найдено, и именно на этом стоит сложность задачи коммивояжёра. Зато есть удобные достаточные условия: теорема Дирака — если степень каждой вершины не меньше $n /2$ , цикл существует; теорема Оре смягчает требование до сумм степеней несмежных пар. Необходимые условия тоже полезны: связность, отсутствие точек сочленения, отсутствие висячих вершин. Что значит NP-полнота и как с ней жить — в уроке сложность алгоритмов.

de g v \geq \frac{n}{2} \forall v \Rightarrow гамильтонов цикл существует

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

Частые вопросы

Чем гамильтонов цикл отличается от эйлерова?

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

Как на практике искать гамильтонов цикл?

Три рабочих подхода. Перебор с отсечениями (поиск в глубину по частичным путям) тянет до двух десятков вершин. Динамическое программирование по подмножествам — алгоритм Хелда—Карпа за $O (n^{2} 2^{n})$ — добирается до $n \approx 25$ . Эвристики вроде 2-opt и метода отжига дают хорошие, но негарантированные маршруты на больших графах. Иногда цикл доказывается без построения — достаточными условиями Дирака или Оре.