Русская Википедия:Гамильтонов граф

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

Шаблон:Main

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

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

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

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

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Добротная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Шаблон:Книга
  2. ↑ Шаблон:Книга
  3. ↑ Шаблон:Статья
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок :1 не указан текст
  5. ↑ Шаблон:Cite web
  6. ↑ Шаблон:Книга
  7. ↑ Шаблон:Книга
  8. ↑ Шаблон:Статья
  9. ↑ Шаблон:Книга
  10. ↑ Шаблон:Книга
  11. ↑ Шаблон:Книга
  12. ↑ 12,0 12,1 12,2 12,3 Ошибка цитирования Неверный тег <ref>; для сносок :0 не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Гамильтонов_граф&oldid=9504534