Дано: ориентированный граф $% G = (V, E) $%, две вершины $%v, w \in V $% и список пар вершин этого графа $$P = (v_1, w_1), \cdots, (v_k, w_k). $$ Спрашивается, существует ли путь в графе от $% v $% до $% w $%, проходящий не более чем через одну вершину каждой пары из $% P?$%

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


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

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

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×273

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

показан
280 раз

обновлен
26 Сен '19 14:07

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

по почте:

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

по RSS:

Ответы

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

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