Задание № 9 · ОГЭ

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

Цикл, который посещает каждую вершину графа ровно один раз

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Гамильтонов циклНазвание происходит от имени ирландского математика Уильяма Гамильтона.

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

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

\[v_1 \to v_2 \to \dots \to v_n \to v_1\]

Здесь \(v_1, v_2, \dots, v_n\) — все вершины графа, причём ни одна из них не повторяется внутри маршрута. Число рёбер гамильтонова цикла равно числу вершин графа: \(n\).

№

Пример

В графе с вершинами A, B, C и D есть рёбра AB, BC, CD и DA. Тогда маршрут A → B → C → D → A — гамильтонов цикл: он посещает каждую из четырёх вершин ровно один раз и возвращается в A.

Не путайте с эйлеровым циклом

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

Проверьте себя

Какой маршрут является гамильтоновым циклом в графе с вершинами A, B, C, D?

Главное за минуту

Главное

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