Цикл Гамильтона

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

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

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

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

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

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

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

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

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

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

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

Условие Поша

Введем следующую функцию 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.(англ.)
• Теория графов и комбинаторика
• Эйлеровы и Гамильтоновы графы

-> методы решения Гамильтоновых графов:

• генетический метод (с программой)
• обсуждение задачи комивояжера