Гамильтонов граф

Граф додекаэдра с выделенным циклом Гамильтона

Гамильтонов путь (чёрным)

Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.

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

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

Условия существования

Необходимое условие

Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x(i) с локальной степенью p(x(i)) < 2. Доказательство следует из определения.

Условие Дирака (англ.) (1952)

Пусть $p$ — число вершин в данном графе; если степень каждой вершины не меньше, чем $\frac{p}{2}$, то граф называется графом Дирака. Граф Дирака — гамильтонов.

Условие Оре (1960)

Пусть $p$ — количество вершин в данном графе. Если для любой пары несмежных вершин $x, y$ выполнено неравенство $d(x)+d(y)\geqslant p$, то граф называется графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Граф Оре — гамильтонов.

Теорема Бонди-Хватала

Теорема Бонди-Хватала (англ.) обобщает утверждения Дирака и Оре. Для графа G с n вершинами замыкание определяется добавлением в G ребра (u,v) для каждой пары несмежных вершин u и v, сумма степеней которых не меньше n.

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф.

Условие Поша

Введем следующую функцию $f(x)$ целого неотрицательного аргумента $x$ на графе $G = [A, B]$:

$f(x) = \left| \left\{ a \in A | d(a) \le x \right\} \right|$.

Написанное означает, что функция $f(x)$ в каждом целом неотрицательном $x$ принимает значение, равное количеству вершин графа $G = [A, B]$, степень которых не превосходит $x$. Такую функцию $f(x)$ называют функцией Поша графа $G$.

См. также

• Эйлеров цикл
• Задача коммивояжёра
• Задача о ходе коня
• Проблема семи мостов Кёнигсберга
• Китайская стена (головоломка)

Ссылки

• Weisstein, Eric W. Hamiltonian Circuit (англ.) на сайте Wolfram MathWorld.
• Теория графов и комбинаторика
• Видеолекция посвященная Эйлеровым и Гамильтоновым графам
• Эйлеровы и Гамильтоновы графы