Loading AI tools
граф, в котором можно пройти по всем вершинам ровно 1 раз Из Википедии, свободной энциклопедии
Гамильтонов граф — граф, содержащий гамильтонов цикл[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа.
Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз[1]. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.
Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз[3]. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра[4].
Простое необходимое и достаточное условие существования гамильтонова цикла неизвестно[5].
Необходимое условие существования гамильтонова цикла в неориентированном графе: если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины с локальной степенью . Доказательство следует из определения.
Условие Поша: Пусть граф G имеет вершин. Если для всякого , , число вершин со степенями меньшими или равными n меньше, чем n, и для нечетного число вершин со степенью не превосходит , то G — гамильтонов граф. Это достаточное условие не является необходимым[6].
Как следствие теоремы Поша, получаем более простые и менее сильные достаточные условия, найденные Дираком и Оре.
В 1952 году было сформулировано условие Дирака существования гамильтонова цикла: пусть — число вершин в данном графе и ; если степень каждой вершины не меньше, чем , то данный граф — гамильтонов[7].
Условие Оре: пусть — количество вершин в данном графе и . Если для любой пары несмежных вершин выполнено неравенство , то данный граф — гамильтонов (другими словами: сумма степеней любых двух несмежных вершин не меньше общего числа вершин в графе)[7].
Теорема Бонди[англ.] — Хватала обобщает утверждения Дирака и Оре. Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. Для графа G с n вершинами замыкание строится добавлением в G ребра (u,v) для каждой пары несмежных вершин u и v, сумма степеней которых не меньше n[8].
При прямом переборе вариантов вершин возможно значительное увеличение средней сложности поиска гамильтонова пути на случайных графах (если гарантируется наличие гамильтонова пути в графе). Для улучшения данного способа можно на каждом шаге перебора при некоторой построенной части цепи проверять, образуют ли оставшиеся вершины связный граф (если не образуют, то цепь не может являться началом гамильтоновой цепи); на каждом шаге перебора при выборе следующей вершины пробовать сначала вершины с наименьшей остаточной степенью (количеством рёбер, ведущих в ещё не посещённые вершины). Кроме того, если это дерево является цепью, то гамильтонов цикл в нём возможен. Иначе (если в дереве есть вершины со степенью не меньше, чем 3) построение гамильтонова цикла невозможно[9].
Гамильтонов цикл используется в системе так называемых протоколов с нулевым разглашением.
Пусть Пегги и Виктор знают один и тот же гамильтонов граф G, причём Пегги знает в нём гамильтонов цикл. Она хочет доказать это Виктору, не раскрывая ему самого цикла. Существует алгоритм того, как она должна действовать[10]:
1. Пегги случайным образом преобразовывает граф G. Передвигая точки и изменяя их метки, она создаёт новый граф H, топологически изоморфный G. Тогда, зная гамильтонов цикл в G, она легко найдет его в H. Если бы она не сама создавала H, то определение изоморфизма между графами было бы слишком сложной задачей, решение которой требует огромного количества времени. Затем она шифрует H и получает граф H'.
2. Пегги передаёт Виктору H'.
3. Виктор просит Пегги либо:
4. Пегги выполняет его просьбу. Она либо:
5. Пегги и Виктор повторяют этапы 1 — 4 n раз.
Если Пегги не обманывает, то она сможет рассказать Виктору любое из доказательств на этапе 3. Однако если гамильтонов цикл для G ей самой неизвестен, она не сможет создать H', удовлетворяющий обоим доказательствам. Правда, Пегги может создать или граф, изоморфный G, или граф с таким же числом вершин и рёбер и правильным гамильтоновым циклом. И, хотя с вероятностью 50 % она может угадать, какое доказательство попросит Виктор на этапе 3, Виктор может повторить протокол достаточное число раз, пока не убедится, что Пегги знает гамильтонов цикл в G.
Коммивояжёру необходимо посетить каждый город в пределах некоторой территории и возвратиться в пункт отправления. Требуется, чтобы путь был как можно короче. Таким образом, исходная задача преобразуется в задачу поиска минимальной протяженности (длительности или стоимости)[11].
Задачу можно переформировать в терминах теории графов — построить такой граф G(X, A), вершины которого соответствуют городам, а ребра — коммуникации между городами. Решение этой задачи ищут среди гамильтоновых циклов построенного графа.
Известно много способов решения этой задачи. Можно выделить методы, разработанные Беллмором и Немхаузером[12], Гарфинкелем и Немхаузером[13], Хелдом и Карпом[14], Стекханом[15]. Также известными решениями задачи коммивояжёра являются метод ветвей и границ и метод последовательного улучшения решения[16].
Полугамильтоновым[17] графом называется граф, содержащий простую цепь, проходящую через каждую его вершину ровно один раз. При этом, всякий гамильтонов граф является полугамильтоновым. Гамильтонов цикл является простым остовным циклом[18].
Суть задачи о гамильтоновом цикле — выяснить, имеет ли заданный граф G гамильтонов цикл. Данная задача является NP-полной[19].
Гамильтонова орцепь орграфа[20] — простая цепь, проходящая через каждую вершину орграфа ровно один раз.
Гамильтоновым орциклом[20] называется орцикл[20] орграфа, который проходит через каждую его вершину.
Орграф называется полугамильтоновым[20], если он имеет гамильтонову орцепь, и гамильтоновым[20], если обладает гамильтоновым орциклом.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.