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

Гамильтонов путь

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

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

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

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

Простой путь, содержащий все вершины графа ровно по одному разу. Рёбра графа, не вошедшие в путь, можно не использовать.

Как записывают путь

Путь записывают последовательностью вершин: \(v_1, v_2, \ldots, v_n\). Каждые две соседние вершины в этой последовательности должны быть соединены ребром, а все \(n\) вершин графа должны встретиться ровно один раз. Поэтому гамильтонов путь содержит \(n-1\) рёбер, где \(n\) — число вершин графа.

\[v_1 \to v_2 \to \ldots \to v_n, \qquad |V|=n, \qquad |E_{\text{пути}}|=n-1\]

№

Пример

Пусть граф имеет вершины \(A\), \(B\), \(C\), \(D\) и рёбра \(AB\), \(BC\), \(CD\), \(AD\). Последовательность \(A \to B \to C \to D\) — гамильтонов путь: все вершины посещены по одному разу, а соседние вершины соединены рёбрами. Ребро \(AD\) в этот путь не входит.

Не путайте с Эйлеровым путём

Эйлеров путь проходит ровно по одному разу через каждое ребро, а гамильтонов — через каждую вершину. Одно и то же прохождение может обладать только одним из этих свойств или обоими сразу.

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

В графе 5 вершин. Сколько рёбер содержит любой гамильтонов путь этого графа?

Если в конце пути последняя вершина соединена с первой, можно замкнуть маршрут. Тогда получится гамильтонов цикл, но наличие гамильтонова пути само по себе не означает, что такой цикл существует.

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

Главное

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