Дано: неориентированный граф $% G = (V, E) $% и две вершины $%s, t \in V $%. Спрашивается, содержит ли граф $% G $% гамильтонов путь из $% s $% в $% t $%?

Докажите, что данная задача является NP-полной, или приведите полиномиальный алгоритм ее решения.


Для доказательства NP-полноты можно использовать NP-полноту следующих задач: 1) выполнимость булевой формулы (SAT); 2) выполнимость 3-КНФ; 3) существование клики заданного размера в графе; 4) существование вершинного покрытия заданного размера в графе; 5) наличие гамильтонова пути в ориентированном графе.

задан 26 Сен '19 14:02

Замените каждое ребро на два ориентированных, и сведите к 5).

(26 Сен '19 14:22) falcao
1

@falcao как учесть в сведении, что в 5) проверяется наличие гамильтонова пути в целом, а в данной задаче - наличие гамильтонова пути между двумя фиксированными вершинами? И, кажется, надо сводить от 5 к данной, то есть от ориентированного графа к неориентированному?

(26 Сен '19 14:31) akakii

@akakii: можно добавить новые вершины u, v и ориентированные рёбра u->s, v->t. Тогда в новом графе существует ориентированный гамильтонов путь тогда и только тогда, когда в старом имеется обычный гамильтонов путь из s в t.

СведЕние одной задачи к другой может подразумевать, что из разрешимости A следует разрешимость B, или что неразрешимость B влечёт неразрешимость A. Поэтому мы вправе сказать, что исходную задачу сводим к 5), рассуждая от противного.

(26 Сен '19 17:45) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×273

задан
26 Сен '19 14:02

показан
587 раз

обновлен
26 Сен '19 17:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru