20
правок
Изменения
м
→Задача о гамильтоновом пути в графе
==Задача о гамильтоновом цикле в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAM}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [неориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова циклагамильтонов цикл]] в заданном графе.
}}
===Доказательство NP-полноты для неориентированного ориентированного графа===
Для доказательства того, что <math>\mathrm{HAM}</math> <math>\in</math> [[NPC|<math>\mathrm{NPC}</math>]], необходимо доказать два факта:
*<math>\mathrm{HAM}</math> <math>\in</math> [[NP|<math>\mathrm{NP}</math>]]
Сведем задачу о выполнимости булевых формул вида [[3CNFSAT | <math>\mathrm{3CNF}</math>]] к <math>\mathrm{HAM}</math>. Начнем построение экземпляра <math>\mathrm{HAM}</math> по булевой формуле в [[3CNFSAT | <math>\mathrm{3CNF}</math>]]. Пусть формула имеет вид <math>E = e_1 \land e_2 \land \ldots \land e_k</math>, где каждое <math>e_i</math> {{---}} дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} \vee \alpha_{i2} \vee \alpha_{i3})</math>. Пусть <math>x_1, x_2, \ldots, x_n</math> {{---}} переменные в формуле <math>E</math>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
Для каждой переменной <math>x_i</math> строится подграф <math>H_i</math> высотой <math>m_i + 2</math>, структура которого показана на рисунке 1. Здесь <math>m_i</math> {{---}} большее из чисел вхождений <math>\bar{x_i}</math> и <math>x_i</math> в <math>E</math>. Узлы <math>c_{ij}</math> и <math>b_{ij}</math>, расположенные в двух столбцах, соединены между собой дугами в обоих направлениях. Кроме того, каждое <math>b</math> имеет дугу, ведущую в <math>c</math>, расположенное на ступеньку ниже, т.е., если <math>j < m_i</math>, то <math>b_{ij}</math> имеет дугу, ведущую в <math>c_{i,j+1}</math>. Аналогично для <math>c_{ij}</math>. Наконец, есть верхний узел <math>a_i</math>, из которого дуги ведут в <math>b_{i0}</math> и <math>c_{i0}</math>, и нижний узел <math>d_i</math>, в который ведут дуги из <math>b_{im_i}</math> и <math>c_{im_i}</math>.
На рисунке 2 показана структура графа в целом. Каждый пятиугольник представляет один подграф, построенный для переменной (его структура показана на рисунке 1. пятиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
Причина в том, что если цикл переходит из <math>a_{i}</math> в <math>b_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>j</math>-й дизъюнкт содержит <math>x_i</math> в качестве одного из литералов. Если цикл переходит из <math>a_i</math> в <math>c_{i0}</math>, то экскурсия в <math>I_{j}</math> может быть совершена только тогда, когда <math>\bar{x_i}</math> является литералом в <math>j</math>-ом дизъюнкте. Таким образом, из того, что все подграфы <math>I_j</math> могут быть включены в граф, следует, что при данной подстановке хотя бы один из литералов в каждом дизъюнкте истинен, т.е. формула <math>E</math> выполнима.
===Доказательство NP-полноты для ориентированного неориентированного графа===
Для доказательства того, что <math>\mathrm{UHAM}</math> <math>\in</math> [[NPC|<math>\mathrm{NPC}</math>]], необходимо доказать два факта:
*<math>\mathrm{UHAM}</math> <math>\in</math> [[NP|<math>\mathrm{NP}</math>]]
==Задача о гамильтоновом пути в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAMP}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [неориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова путигамильтонов путь]] в заданном графе.
}}
* [[3CNFSAT]]
* [[Примеры NP-полных языков]]
* [[Гамильтоновы графы#Задача о коммивояжере | Задача о коммивояжере]]
==Источники информации==
* Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" {{---}} Издательский дом «Вильямс», 2000. {{---}} С. 384. {{---}} ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.)
* Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е издание. {{---}} М.: Издательский дом "Вильямс", 2002. {{---}} 528 с. {{---}} ISBN 5-8459-0261-4 (рус.)z
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Примеры NP-полных языков]]
