Эта статья является кандидатом в добротные статьи

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа.

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

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

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

Условия существования[править | править вики-текст]

Необходимое условие существования гамильтонова пути в неориентированном графе: если неориентированный граф 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 — гамильтонов граф. Это достаточное условие не является необходимым[5].

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

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

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

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

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

Алгоритм поиска гамильтонова пути[править | править вики-текст]

Эвристические оптимизации[править | править вики-текст]

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

Примеры использования[править | править вики-текст]

Криптография[править | править вики-текст]

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

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

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.

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

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

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

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

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

Связанные термины[править | править вики-текст]

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

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 М. О. Асанов, В. А. Баранский, В. В. Расин Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 41. — ISBN 5-93972-076-5.
  2. М. Свами, К. Тхуласираман Графы, сети и алгоритмы. — Москва: Мир, 1984. — С. 55.
  3. Ф. Харари Теория графов. — г. Москва, пр-т 60-летия Октября, 9: Едиториал УРСС, 2003. — С. 16-17.
  4. О. Оре Графы и их применение. — Москва: Мир, 1965. — С. 40-41.
  5. Ф. Харари Теория графов. — второе. — Москва: УРСС, 2003. — С. 86. — ISBN 5-354-00301-6.
  6. 1 2 Ф. Харари Теория Графов. — Москва: УРСС, 2003. — С. 87. — ISBN 5-354-00301-6.
  7. Свами М., Тхуласираман К. Графы, сети и алгоритмы.. — Москва: Мир, 1984. — С. 61.
  8. [http://www.intuit.ru/studies/courses/101/101/lecture/2957?page=3 Графы и алгоритмы: Лекция 8: Эйлеровы и гамильтоновы циклы]. НОУ Интуит.
  9. Брюс Шнайер Прикладная криптография. — "Триумф", 2002. — С. 89-90.
  10. Э. Майника Алгоритмы оптимизации на сетях и графах. — Москва: Мир, 1981. — С. 241-264.
  11. Bellmore M., Nemhuser G. L. The Travelling Salesman Problem: A. Survey. — ORSA vol. 16, 1968. — С. pp 538-558.
  12. Garfinkel R., Namhauser G. L. Integer Programming. — New York: John Wiley, Inc.,, 1972. — С. pp 354-360.
  13. Held M., Karp R. The Travelling-Salesman Problem and Minimum Spanning Trees, Part II. — Math. Programming, vol. 1, No., 1971. — С. pp. 6-25.
  14. Steckhan H. A. Theorem on Symmetric Travelling Salesman Problems. — ORSA, vol. 18, 1970. — С. pp. 1163-1167.
  15. Э. Майника Алгоритмы оптимизации на сетях и графах. — Москва: "Мир", 1981. — С. 255-264.
  16. Уилсон И.Р., Эддиман А.М. Практическое введение в Паскаль. — Москва: Радио и связь, 1983. — С. 143.
  17. У. Татт Теория графов. — Москва: Мир, 1988. — С. 26. — ISBN 5-03-001001-7.
  18. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ. — Москва: МЦНМО, 2002. — С. 845-846.
  19. 1 2 3 4 5 Б. А. Долгих,А. А. Петренко Дискретная математика. — Москва, 2007. — С. 126. — ISBN 978-5-276-01103-5.

Литература[править | править вики-текст]

  • Б. Шнайер Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке C. — Триумф, 2002.
  • К. Берж Теория графов и ее применение. — Москва: Иностранной литературы, 1962.
  • Р. Уилсон Введение в теорию графов. — Москва: Мир, 1977.
  • У. Татт Теория графов. — Москва: Мир. — Т. 1988.
  • Н. Кристофидес Теория Графов. — Москва: Мир, 1978.
  • Б. А. Долгих,А. А. Петренко Дискретная математика. — Москва, 2007. — С. 126. — ISBN 978-5-276-01103-5.

Ссылки[править | править вики-текст]