Гамильтонова проблема пути - Hamiltonian path problem

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

Сложность

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

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

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

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

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

использованная литература

СМИ, связанные с Гамильтонова проблема пути в Wikimedia Commons

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