Изменения
Нет описания правки
==Задача о гамильтоновом цикле в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAM}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [ориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова циклагамильтонов цикл]] в заданном графе.
}}
===Доказательство NP-полноты для неориентированного графа===
Сведем задачу о выполнимости булевых формул вида [[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. пятиугольники расположены циклически, и из нижнего узла каждого подграфа дуга ведет в верхний узел следующего.
==Задача о гамильтоновом пути в графе==
{{Определение
|definition = '''<math>\mathrm{[U]HAMP}</math>''' {{---}} задача нахождения (ориентированного) язык графов, содержащих [ориентированный] [[Гамильтоновы графы#Основные определения|гамильтонова путигамильтонов путь]] в заданном графе.
}}
* [[3CNFSAT]]
* [[Примеры NP-полных языков]]
* [[Гамильтоновы графы#Задача о коммивояжере | Задача о коммивояжере]]
==Источники информации==
