Редактирование: NP-полнота задач о гамильтоновом цикле и пути в графах

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 11: Строка 11:
 
====Доказательство принадлежности к NPH====
 
====Доказательство принадлежности к NPH====
  
[[Файл:HAM_fig1.png|200px|thumb|right|Рисунок 1.]] [[Файл:HAM_fig2.png|200px|thumb|right|Рисунок 2.‎]] [[Файл:HAM_fig3.png|200px|thumb|right|Рисунок 3.‎]] [[Файл:HAM_fig4.png|200px|thumb|right|Рисунок 4.]]
+
[[Файл:HAM_fig1.png|200px|thumb|right|Рисунок 1]] [[Файл:HAM_fig2.png|200px|thumb|right|Рисунок 2‎]] [[Файл:HAM_fig3.png|200px|thumb|right|Рисунок 3‎]] [[Файл:HAM_fig4.png|200px|thumb|right|Рисунок 4]]
  
Сведем задачу о выполнимости булевых формул вида [[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>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
+
Сведем задачу о выполнимости булевых формул вида [[3CNFSAT | <math>\mathrm{3-КНФ}</math>]] к <math>\mathrm{HAM}</math>. Начнем построение экземпляра <math>\mathrm{HAM}</math> по булевой формуле в 3КНФ. Пусть формула имеет вид <math>E = e_1 \land e_2 \land \ldots \land e_k</math>, где каждое <math>e_i</math> {{---}} дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} + \alpha_{i2} + \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>.
 
Для каждой переменной <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>.
Строка 66: Строка 66:
 
В качестве сертификата возьмем гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
 
В качестве сертификата возьмем гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
 
====Доказательство принадлежности к NPH====
 
====Доказательство принадлежности к NPH====
Сведем задачу о гамильтоновом цикле <math>\mathrm{HAM}</math> к <math>\mathrm{UHAM}</math>. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую {{---}} с третьей. Для каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся (см. рисунок 4). Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
+
Сведем задачу о гамильтоновом цикле (<math>\mathrm{HAM}</math> к <math>\mathrm{UHAM}</math>. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую {{---}} с третьей. Для каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся (см. рисунок 4). Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
  
 
==Задача о гамильтоновом пути в графе==
 
==Задача о гамильтоновом пути в графе==
Строка 89: Строка 89:
 
В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
 
В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
 
====Доказательство принадлежности к NPH====
 
====Доказательство принадлежности к NPH====
Сведем задачу о гамильтоновом пути в ориентированном графе <math>\mathrm{HAMP}</math> к <math>\mathrm{UHAMP}</math>. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую {{---}} с третьей. Для каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
+
Сведем задачу о гамильтоновом цикле (<math>\mathrm{HAMP}</math>) к <math>\mathrm{UHAMP}</math>. Пусть дан ориентированный граф <math>G</math>. Построим по нему неориентированный граф <math>H</math>. Для этого каждой вершине из графа <math>G</math> поставим в соответствие 3 вершины в графе <math>H</math>, соединив в <math>H</math> ребром первую получившуюся со второй, а вторую {{---}} с третьей. Для каждой дуги, инцидентной исходной вершине в <math>G</math> поставим в соответствие ребро в <math>H</math>. В случае, если дуга исходит из этой вершины, то соединим ребро с последней из получившихся вершин в <math>H</math>, а если она входит в вершину, то соединим с первой из получившихся. Таким образом, в построенном графе <math>H</math> гамильтонов путь будет тогда и только тогда, когда в исходном графе <math>G</math> будет ориентированный гамильтонов путь.
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: