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

Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа.

Примеры гамильтоновых циклов на графе квадратной решетки 8x8.

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

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

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра.

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

Простое необходимое и достаточное условие существования гамильтонова цикла неизвестно.

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

Условие Поша: Пусть граф G имеет $p>2$ вершин. Если для всякого $n$, $0<n<(p-1)/2$, число вершин со степенями меньшими или равными n меньше, чем n, и для нечетного $p$ число вершин со степенью $(p-1)/2$ не превосходит $(p-1)/2$, то G — гамильтонов граф. Это достаточное условие не является необходимым.

Как следствие теоремы Поша, получаем более простые и менее сильные достаточные условия, найденные Дираком и Оре.

В 1952 году было сформулировано условие Дирака существования гамильтонова цикла: пусть $p$ — число вершин в данном графе и $p>3$; если степень каждой вершины не меньше, чем ${\frac {p}{2}}$, то данный граф — гамильтонов.

Основная статья: Теорема Оре

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

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

Алгоритм поиска гамильтонова пути

Эвристические оптимизации

При прямом переборе вариантов вершин возможно значительное увеличение средней сложности поиска гамильтонова пути на случайных графах (если гарантируется наличие гамильтонова пути в графе). Для улучшения данного способа можно на каждом шаге перебора при некоторой построенной части цепи проверять, образуют ли оставшиеся вершины связный граф (если не образуют, то цепь не может являться началом гамильтоновой цепи); на каждом шаге перебора при выборе следующей вершины пробовать сначала вершины с наименьшей остаточной степенью (количеством рёбер, ведущих в ещё не посещённые вершины). Кроме того, если это дерево является цепью, то гамильтонов цикл в нём возможен. Иначе (если в дереве есть вершины со степенью не меньше, чем 3) построение гамильтонова цикла невозможно.

Примеры использования

Криптография

Гамильтонов цикл используется в системе так называемых протоколов с нулевым разглашением.

Пусть Пегги и Виктор знают один и тот же гамильтонов граф G, причём Пегги знает в нём гамильтонов цикл. Она хочет доказать это Виктору, не раскрывая ему самого цикла. Существует алгоритм того, как она должна действовать:

1. Пегги случайным образом преобразовывает граф G. Передвигая точки и изменяя их метки, она создаёт новый граф H, топологически изоморфный G. Тогда, зная гамильтонов цикл в G, она легко найдет его в H. Если бы она не сама создавала H, то определение изоморфизма между графами было бы слишком сложной задачей, решение которой требует огромного количества времени. Затем она шифрует H и получает граф H'.

2. Пегги передаёт Виктору H'.

3. Виктор просит Пегги либо:

1. Доказать, что H' — зашифрованная изоморфная копия G, либо
2. Показать гамильтонов цикл для H.

4. Пегги выполняет его просьбу. Она либо:

1. Доказывает, что H' — зашифрованная изоморфная копия G, раскрывая преобразования и всё расшифровывая, не показывая гамильтонов цикл для G или H, либо
2. Показывает гамильтонов цикл для H, расшифровывая только то, что образует гамильтонов цикл, не доказывая, что H и G топологически изоморфны.

5. Пегги и Виктор повторяют этапы 1 — 4 n раз.

Если Пегги не обманывает, то она сможет рассказать Виктору любое из доказательств на этапе 3. Однако если гамильтонов цикл для G ей самой неизвестен, она не сможет создать H', удовлетворяющий обоим доказательствам. Правда, Пегги может создать или граф, изоморфный G, или граф с таким же числом вершин и рёбер и правильным гамильтоновым циклом. И, хотя с вероятностью 50 % она может угадать, какое доказательство попросит Виктор на этапе 3, Виктор может повторить протокол достаточное число раз, пока не убедится, что Пегги знает гамильтонов цикл в G.

Экстремальные задачи теории графов: Задача коммивояжёра

Основная статья: Задача коммивояжёра

Коммивояжёру необходимо посетить каждый город в пределах некоторой территории и возвратиться в пункт отправления. Требуется, чтобы путь был как можно короче. Таким образом, исходная задача преобразуется в задачу поиска минимальной протяженности (длительности или стоимости).

Задачу можно переформировать в терминах теории графов — построить такой граф G(X, A), вершины которого соответствуют городам, а ребра — коммуникации между городами. Решение этой задачи ищут среди гамильтоновых циклов построенного графа.

Известно много способов решения этой задачи. Можно выделить методы, разработанные Беллмором и Немхаузером, Гарфинкелем и Немхаузером, Хелдом и Карпом, Стекханом. Также известными решениями задачи коммивояжёра являются метод ветвей и границ и метод последовательного улучшения решения.

Связанные термины

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

Суть задачи о гамильтоновом цикле — выяснить, имеет ли заданный граф G гамильтонов цикл. Данная задача является NP-полной.

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

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

Орграф называется полугамильтоновым, если он имеет гамильтонову орцепь, и гамильтоновым, если обладает гамильтоновым орциклом.

См. также

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

Литература

• Ф. Харари. Теория графов. — М.: УРСС, 2003. — ISBN 5-354-00301-6.
• Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — Триумф, 2002.
• К. Берж. Теория графов и её применение. — Москва: Издательство иностранной литературы, 1962.
• Р. Уилсон. Введение в теорию графов. — Москва: Мир, 1977.
• У. Татт. Теория графов. — Москва: Мир, 1988. — ISBN 5-03-001001-7.
• Н. Кристофидес. Теория Графов. — Москва: Мир, 1978.
• Б. А. Долгих, А. А. Петренко. Дискретная математика. — Москва: МГИУ, 2007. — С. 126—127. — ISBN 978-5-276-01103-5.
• М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. — Москва: Мир, 1984.
• Э. Майника. Алгоритмы оптимизации на сетях и графах. — Москва: Мир, 1981.

Ссылки

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