Неориентированный гамильтонов цикл и задача коммивояжера

С задачей о неориентированном гамильтоновом цикле (ГЦ) связана задача о коммивояжере (КОМ). В этой задаче требуется найти оптимальный маршрут посещения n городов. Коммивояжер хочет объехать все города, побывав в каждом ровно по одному разу, и вернуться в город, из которого начато путешествие. Переезд из города i в город j стоит c(i, j) рублей. В терминах теории графов задача формулируется так: требуется найти в данном графе неориентированный гамильтонов цикл (ГЦ) наименьшей стоимости. Язык КОМ = {<G,c,k> : G = (V, E)- полный граф, c : V´V®Z – функция стоимости, kÎZ и в G есть гамильтонов цикл стоимости не более k}.

В терминанах машины Тьюринга постановка задачи выглядит так:

вход КОМ - это граф, каждое ребро которого имеет целочисленный вес, и число W – предельный вес. Вопрос состоит в том, есть ли в графе гамильтонов цикл с общим весом, не превышающим W. Решение проблемы КОМ есть перебор всех циклов и подсчет общего веса каждого из них. На многоленточной НМТ перестановку можно угадать за O(n²) шагов, и столько же времени потребуется для подсчета ее общего веса . Таким образом, проблемы ГЦ и КОМ принадлежит классу NP.

Теорема.Проблема ГЦ NP-полна.

Доказательство. Проблема ОГЦ сводится к проблеме ГЦследующим образом. По ориентированному графу G строится неориентированный граф G^’, где каждому узлу n графа G соответствуют три узла графа G^’- n⁰,n¹,n² , а дуге (ребру) (n,w) графа G соответствует четыре ребра в графе G^’ (рис. 10.11): (n⁰,n¹), (n¹,n²), (n²,w⁰), (w⁰,w¹), (w¹,w²).

Построение G^’ по G выполнимо за полиномиальное время.

Рис.10.11.

Покажем, что G^’ имеет гамильтонов цикл тогда и только тогда, когда G имеет ориентированный гамильтонов цикл.

Достаточность. Пусть n₁,n₂,…,n_m,n₁ – ориентированный гамильтонов цикл. Тогда n₁⁰,n₁¹,n₁²,n₂⁰,n₂¹,n₂²,…,n_n⁰,n_n¹,n_n²,n₁⁰ есть неориентированный гамильтонов цикл в G^’. Таким образом, происходит спуск по каждому столбцу, а затем скачок на вершину следующего столбца, соответствующий дуге в G.

Необходимость. Как следует из построения, гамильтонов цикл в G^’ должен содержать узлы, индексы которых образуют последовательность

0,1,2,0,1,2,… (или 2,1,0,2,1,0,…) . Ребра, соединяющие вершины с индексами 2 и 0 (или 0 и 2) являются дугами графа G и направление обхода таких ребер совпадает с направлением соответствующих дуг. Таким образом, существование неориентированного гамильтонова цикла в G^’ влечет существование ориентированного гамильтонова цикла в G. “

Теорема.Задача коммивояжера (язык КОМ) является NP-полной.

Доказательство Проблема ГЦ сводится к проблеме КОМ следующим образом. По данному графу G строится взвешенный граф G^*, который имеет те же узлы и ребра, что и G, каждое ребро которого имеет вес 1.

Предельное значение W берется равным n –числу вершин G. Таким образом, в G^* существует гамильтонов цикл с весом n тогда и только тогда, когда существует гамильтонов цикл в G. “