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

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

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

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

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

Проблемы поиска гамильтонова пути и гамильтонова цикла можно связать следующим образом:

  • В одном направлении, гамильтонова проблема пути для графа G может быть связана с проблемой гамильтонова циклом в графе H , полученной из G путем добавления новой универсальной вершины х , соединяющее х ко всем вершинам G . Таким образом, поиск гамильтонова пути не может быть значительно медленнее (в худшем случае, в зависимости от числа вершин), чем поиск гамильтонова цикла.
  • С другой стороны, проблема гамильтонова цикла для графа G эквивалентна задаче гамильтонова пути в графе H, полученном добавлением терминальных ( один степени ) вершин s и t, прикрепленных соответственно к вершине v графа G и к v ', расщепляется копия из V , который дает у» ту же окрестность , как против . Гамильтонов путь в H, проходящий через вершины svx -...- y-v'-t, соответствует гамильтонову циклу в G, проходящему через vx -...- y (-v) .

Алгоритмы

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

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

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

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

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

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

Сложность

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

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

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

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

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

Рекомендации

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