Из Википедии, свободной энциклопедии
  (Перенаправлено из задачи о гамильтоновом цикле )
Перейти к навигации Перейти к поиску
Эта статья посвящена конкретной проблеме определения того, существует ли гамильтонов путь или цикл в данном графе. Общие концепции теории графов см. В разделе Гамильтонов путь .

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

Задача о гамильтоновом цикле - это частный случай задачи коммивояжера , полученная установкой расстояния между двумя городами равным одному, если они смежны, и двум в противном случае, и проверке того, что общее пройденное расстояние равно n (если да, то маршрут равен гамильтонова схема; если нет гамильтоновой схемы, кратчайший маршрут будет длиннее).

Сокращение между проблемой пути и проблемой цикла [ править ]

Существует простая связь между задачами поиска гамильтонова траектории и гамильтонова цикла:

  • В одном направлении проблема гамильтонова пути для графа G эквивалентна проблеме гамильтонова цикла в графе H, полученном из G путем добавления новой вершины x и соединения x со всеми вершинами графа G. Таким образом, поиск гамильтонова пути не может быть значительно медленнее. (в худшем случае в зависимости от числа вершин), чем нахождение гамильтонова цикла.
  • С другой стороны, проблема гамильтонова цикла для графа G эквивалентна задаче гамильтонова пути в графе H, полученном копированием одной вершины v графа G, v ', то есть позволяя v' иметь ту же окрестность, что и v, и добавив две фиктивные вершины первой степени и соединив их с вершинами v и v 'соответственно. [2]

Алгоритмы [ править ]

Есть n ! различные последовательности вершин, которые могут быть гамильтоновыми путями в данном графе с n вершинами (и являются в полном графе ), поэтому алгоритм поиска методом грубой силы , который проверяет все возможные последовательности, будет очень медленным. Первым точным алгоритмом поиска гамильтонова цикла на ориентированном графе был алгоритм перечисления Мартелло. [3] Процедура поиска Фрэнка Рубина [4]делит ребра графа на три класса: те, которые должны быть на пути, те, которые не могут быть на пути, и не определившиеся. По мере продолжения поиска набор правил принятия решений классифицирует нерешенные ребра и определяет, следует ли остановить или продолжить поиск. Алгоритм делит граф на компоненты, которые можно решить отдельно. Кроме того, алгоритм динамического программирования Беллмана, Хелда и Карпа может быть использован для решения задачи за время O ( n 2  2 n ). В этом методе для каждого набора вершин S и каждой вершины v в S определяется, существует ли путь, который охватывает точно вершины в S и заканчивается вv . Для каждого выбора S и v путь существует для ( S , v ) тогда и только тогда, когда у v есть сосед w такой, что путь существует для ( S  -  v , w ), который можно найти по уже вычисленной информации в динамической программе. [5] [6]

Андреас Бьёрклунд предложил альтернативный подход, использующий принцип включения-исключения, чтобы свести проблему подсчета количества гамильтоновых циклов к более простой проблеме подсчета, подсчета покрытий циклов, которую можно решить путем вычисления определенных матричных определителей. Используя этот метод, он показал, как решить задачу гамильтонова цикла в произвольных n -вершинных графах с помощью алгоритма Монте-Карло за время O (1,657 n ); для двудольных графов этот алгоритм можно улучшить до времени o (1,415 n ). [7]

Для графов максимальной степени три тщательный поиск с возвратом может найти гамильтонов цикл (если он существует) за время O (1,251 n ). [8]

Гамильтоновы пути и циклы можно найти с помощью решателя SAT .

Из-за сложности решения гамильтоновых задач о путях и циклах на обычных компьютерах они также изучались в нетрадиционных моделях вычислений. Например, Леонард Адлеман показал, что проблема гамильтонова пути может быть решена с помощью компьютера ДНК . Используя параллелизм, присущий химическим реакциям, проблема может быть решена с использованием ряда шагов химической реакции, линейных по количеству вершин графа; однако для участия в реакции требуется определенное количество молекул ДНК. [9]

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

Сложность [ править ]

Проблема поиска гамильтонова цикла или пути находится в FNP ; аналогичная проблема решения состоит в том, чтобы проверить, существует ли гамильтонов цикл или путь. Задачи с направленным и неориентированным гамильтоновым циклом были двумя из 21 NP-полной проблемы Карпа . Они остаются NP-полными даже для особых видов графов, таких как:

  • двудольные графы , [11]
  • неориентированные плоские графы максимальной степени три, [12]
  • ориентированные плоские графы со степенью выхода и степенью не выше двух, [13]
  • безмостовые неориентированные плоские 3- правильные двудольные графы ,
  • 3-связные 3-регулярные двудольные графы, [14]
  • подграфы графа с квадратной сеткой , [15]
  • кубические подграфы графа с квадратной сеткой. [16]

Однако для некоторых специальных классов графов проблема может быть решена за полиномиальное время:

  • Четырехсвязные плоские графы всегда гамильтоновы по результату Тютта , и вычислительная задача по нахождению гамильтонова цикла в этих графах может быть выполнена за линейное время [17] путем вычисления так называемого пути Тутта .
  • Тутте доказал этот результат, показав, что каждый 2-связный плоский граф содержит путь Тутте. Пути Тутте, в свою очередь, могут быть вычислены за квадратичное время даже для двухсвязных плоских графов [18], которые могут использоваться для нахождения гамильтоновых циклов и длинных циклов в обобщениях плоских графов.

Собирая все эти условия вместе, остается открытым, должны ли 3-связные 3-регулярные двудольные плоские графы всегда содержать гамильтонов цикл, и в этом случае проблема, ограниченная этими графами, не может быть NP-полной; см . гипотезу Барнетта .

В графах, в которых все вершины имеют нечетную степень, аргумент, связанный с леммой о подтверждении связи, показывает, что количество гамильтоновых циклов, проходящих через любое фиксированное ребро, всегда четно, поэтому, если задан один гамильтонов цикл, то должен существовать и второй. [19] Однако поиск этого второго цикла не кажется легкой вычислительной задачей. Пападимитриу определил PPA класса сложности для инкапсуляции таких проблем, как эта. [20]

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

СМИ, связанные с проблемой гамильтонова пути на Викискладе?

  1. ^ Майкл Р. Гэри и Дэвид С. Джонсон (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, стр. 199–200.
  2. ^ Сведение от гамильтонова цикла к гамильтонову пути
  3. ^ Мартелло, Silvano (1983), "перечислительной алгоритм поиск гамильтоновых цепей в ориентированном графе", ACM Сделки по математическому Software , 9 (1): 131-138, да : 10,1145 / 356022,356030
  4. ^ Рубин, Франк (1974), "Обыск Порядок Гамильтон путей и контуров", Журнал ACM , 21 (4): 576-80, DOI : 10,1145 / 321850,321854
  5. ^ Беллмана, Р. (1962), «Динамическое программирование обработка задачи коммивояжера», журнал АКМ , 9 : 61-63, DOI : 10,1145 / 321105,321111.
  6. ^ Held, M .; Карп, Р. М. (1962), "Динамическое программирование подход к проблемам секвенирования" (PDF) , Дж SIAM , 10 (1): 196-210, DOI : 10,1137 / 0110015 , ЛВП : 10338.dmlcz / 103900 .
  7. ^ Björklund, Андреас (2010), "Детерминантные суммы для неориентированной гамильтоничности", Proc. 51-й симпозиум IEEE по основам информатики (FOCS '10) , стр. 173–182, arXiv : 1008.0541 , doi : 10.1109 / FOCS.2010.24 , ISBN 978-1-4244-8525-3.
  8. ^ Ивама, Кадзуо; Накашима, Такуя (2007), "Улучшенный точный алгоритм для кубического графа TSP", Proc. 13 - я ежегодная Международная конференция по вычислительной и комбинаторика (КОКОН 2007) , Lecture Notes в области компьютерных наук, 4598 , стр 108-117,. CiteSeerX 10.1.1.219.1672 , DOI : 10.1007 / 978-3-540-73545-8_13 , ISBN  978-3-540-73544-1.
  9. ^ Адлеман, Леонард (ноябрь 1994 г.), «Молекулярное вычисление решений комбинаторных задач», Science , 266 (5187): 1021–1024, Bibcode : 1994Sci ... 266.1021A , CiteSeerX 10.1.1.54.2565 , doi : 10.1126 / science.7973651 , JSTOR 2885489 , PMID 7973651   .
  10. ^ Михай Oltean (2006). Устройство на основе света для решения задачи о гамильтоновой траектории . Нетрадиционные вычисления. Springer LNCS 4135. С. 217–227. arXiv : 0708.1496 . DOI : 10.1007 / 11839132_18 .
  11. ^ «Доказательство того, что существование пути Гамильтона в двудольном графе является NP-полным» . Обмен стеком информатики . Проверено 18 марта 2019 .
  12. ^ Garey, MR ; Джонсон, DS ; Stockmeyer, L. (1974), "Некоторые упрощенные NP-полные проблемы", Proc. 6-й симпозиум ACM по теории вычислений (STOC '74) , стр. 47–63, DOI : 10.1145 / 800119.803884.
  13. ^ Плесник, J. (1979), "NP-полнота задачи гамильтонова цикла в плоских орграфах со степенью связаны два" (PDF) , Information Processing Letters , 8 (4): 199-201, DOI : 10.1016 / 0020- 0190 (79) 90023-1 .
  14. ↑ Акияма, Таканори; Нишизэки, Такао ; Сайто, Нобуджи (1980–1981), "NP-полнота проблемы гамильтонова цикла для двудольных графов", Журнал обработки информации , 3 (2): 73–76, MR 0596313 .
  15. ^ Итаи, Алон; Пападимитриу, Христос; Szwarcfiter, Джейм (1982), "Гамильтон Дорожки в Grid - графах", SIAM журнал по вычислениям , 4 (11): 676-686, CiteSeerX 10.1.1.383.1078 , DOI : 10,1137 / 0211056 .
  16. ^ Buro, Майкл (2000), «Простые амазонки эндшпиль и их подключение к цепям Гамильтон в кубических графах подсеточных» (PDF) , конференция по компьютерам и играм , Lecture Notes в области компьютерных наук, 2063 , стр. 250-261, CiteSeerX 10.1. 1.40.9731 , DOI : 10.1007 / 3-540-45579-5_17 , ISBN   978-3-540-43080-3.
  17. ^ Чиба, Норишиге; Nishizeki, Такао (1989), "Проблема гамильтонов цикл является линейным времени разрешимы для 4-связных плоских графов", журнал алгоритмов , 10 (2): 187-211, DOI : 10,1016 / 0196-6774 (89) 90012- 6
  18. ^ Шмид, Андреас; Шмидт, Йенс М. (2018), «Computing Tutte Paths», Труды 45-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'18), чтобы выйти в свет.
  19. ^ Томасон, А. Г. (1978), «Гамильтоновы циклы и уникально края благовидных графов», Авансы в теории графов (Кембридж Комбинаторных Conf., Тринити - колледж, Кембридж, 1977) , Annals дискретной математики, 3 , стр.  259-268 , дои : 10.1016 / S0167-5060 (08) 70511-9 , ISBN 9780720408430, MR  0499124.
  20. ^ Пападимитриу, Христос Х. (1994), «О сложности аргумента четности и других неэффективных доказательствах существования», Журнал компьютерных и системных наук , 48 (3): 498–532, CiteSeerX 10.1.1.321.7008 , doi : 10.1016 / S0022-0000 (05) 80063-7 , MR 1279412  .