Ультрагамильтонов цикл
Ультрагамильтонов цикл определяется как закрытый обход, который посещает каждую вершину ровно один раз, за исключением не более одной вершины, которая посещает более одного раза.
Вопрос: - Докажите, что NP-сложно определить, содержит ли данный граф ультрагамильтонов цикл.
Мы можем свести ее к проблеме гамильтонова цикла, которая является NP-сложной проблемой, но я не понимаю, с чего начать, чтобы свести ее к проблеме ультра-гамильтонова цикла.
Подскажите, как это сделать?
1 ответ
Мы знаем, что проблема гамильтонова пути, как известно, является NP-полной. Теперь, чтобы доказать, что ультрагамильтонов цикл является NP-трудным, мы сведем проблему гамильтонова пути к задаче ультра гамильтонова цикла. Чтобы доказать: гамильтонов путь ≤P ультра-гамильтонова цикла. Доказательство: для каждого случая задачи гамильтонова пути, состоящего из графа G =(V, E) в качестве входных данных, можно преобразовать в задачу ультрагамильтонова цикла, состоящую из графа G '= (V ', E'). Мы построим граф G 'следующим образом: V' = Добавить вершины V исходного графа G и добавить 5-дополнительные вершины V0 V1 V2 V3V4 в форме бабочки (объяснено ниже), так что каждая и каждая вершина графа исходный граф G соединен с вершинами V3 и V4. Здесь, в Графике G 'количество вершин увеличивается на 5, V' = V +5.E '= Добавить ребра E исходного графа G и добавить новые ребра между вновь добавленными вершинами V3 и V4 ко всем исходным вершинам графа G. In G' Количество ребер увеличивается на количество вершин 2V. Эти 5 добавленных вершин (V0 V1 V2 V3V4) находятся в графе бабочки с V0 в качестве точки сочленения. Новый граф G 'может быть получен за полиномиальное время. Подтверждение редукции может быть доказано следующими двумя утверждениями:i)(Прямое направление) Предположим, что граф G содержит гамильтонов путь, охватывающий V вершин графа, начинающийся в случайной вершине, скажем Vstart, и заканчивающийся в Vend, теперь так как мы соединили все вершины с двумя новыми вершинами V3 и V4 в G '. Мы расширяем исходный гамильтонов путь до ультра-гамильтонова цикла, используя ребра Vend до V3 и V4 до Vstart соответственно.Граф G 'теперь содержит цикл, пересекающий все вершины ровно один раз, кроме V0 (точка сочленения в графе бабочки), который посещается более одного раза, этот обход начинается от V0 к V1, затем V2, затем V0, V4, V4, Vstart, чтобы ”гамильтонов путь в G »Для продажи от V3 до V0. (Здесь V0 V1 V2 V3V4 - это график бабочки). Итак, это ультрагамильтонов путь в G '..ii)(направление назад). Мы предполагаем, что граф G 'имеет ультра-гамильтонов цикл, проходящий через все вершины, включая V0 V1 V2 V3V4, поскольку V0 является точкой сочленения, поэтому его нужно посещать более одного раза, и никакие другие вершина посещается более одного раза, также путь из Графика G может войти в граф бабочки в V3 или V4 и оставить граф бабочки в V3 или V4 (в зависимости от того, что не используется для входа в граф бабочки).Как только путь покинет граф-бабочка, он посетит каждую вершину графа G в пути и вернется в граф-бабочка (чтобы никогда не вернуться в вершину графа G). Этот путь должен использовать один из V3 и V4 для выхода, а другой - для входа из графа бабочки в вершины графа G (Ad V0 является точкой сочленения и уже посещается более одного раза, поэтому никакая другая вершина не может быть посещена более одного раза). Теперь, чтобы преобразовать его в гамильтонов путь, мы удалим все ребра, соответствующие вершине V0 V1 V2 V3V4 в цикле. Результирующий путь будет покрывать вершины V графа и покрывать их ровно один раз. Итак, здесь мы получаем гамильтонов путь в G из ультра-гамильтонова цикла в G 'Таким образом, мы можем сказать, что граф G' содержит ультрагамильтонов цикл тогда и только тогда, когда граф G содержит гамильтонов путь. Следовательно,любой пример проблемы ультра-гамильтонова цикла можно свести к примеру проблемы гамильтонова пути. Таким образом, ультра-гамильтонов цикл является NP-трудным.