|
|
| (не показано 6 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | ==Определения==
| + | #REDIRECT [[NP-полнота задач о гамильтоновом цикле и пути в графах]] |
| − | ===Определение 1===
| |
| − | '''Гамильтоновым путем''' в графе <math>G</math> называется упорядочение всех узлов <math>n_{1}</math>, <math>n_{2}</math>, ..., <math>n_{k}</math>, при котором для каждого <math>i = 1, 2, ..., k - 1</math> существует ребро из <math>n_{i}</math> в <math>n_{i+1}</math>.
| |
| − | | |
| − | '''Ориентированным гамильтоновым путем''' называется то же самое для ориентированного графа (должна существовать дуга из <math>n_{i}</math> в <math>n_{i+1}</math>).
| |
| − | | |
| − | ===Определение 2===
| |
| − | '''Гамильтоновым циклом''' в графе <math>G</math> называется упорядочение всех узлов <math>n_{1}</math>, <math>n_{2}</math>, ..., <math>n_{k}</math>, при котором для каждого <math>i = 1, 2, ..., k - 1</math> существует ребро из <math>n_{i}</math> в <math>n_{i+1}</math>, а также существует ребро из <math>n_{k}</math> в <math>n_{1}</math>.
| |
| − | | |
| − | '''Ориентированным гамильтоновым циклом''' называется то же самое для ориентированного графа (должна существовать дуга из <math>n_{i}</math> в <math>n_{i+1}</math> и дуга из <math>n_{k}</math> в <math>n_{1}</math>).
| |
| − | | |
| − | ==Формулировка задачи о гамильтоновом цикле в графе==
| |
| − | В '''задаче об (ориентированном) гамильтоновом цикле в графе''' ([U]HAM) в качестве входных данных выступает (ориентированный) граф <math>G</math>. Требуется выяснить, есть ли в заданном (ориентированном) графе <math>G</math> (ориентированный) гамильтонов цикл.
| |
| − | | |
| − | ==Доказательство NP-полноты задачи об ориентированном гамильтоновом цикле в графе (HAM)==
| |
| − | Для доказательства того, что HAMP <math>\in</math> [[NPC]], необходимо доказать два факта:
| |
| − | *HAM <math>\in</math> [[NP]]
| |
| − | *HAM <math>\in</math> [[NPH]]
| |
| − | ===Доказательство принадлежности к NP===
| |
| − | В качестве сертификата возьмем ориентированный гамильтонов цикл в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
| |
| − | ===Доказательство принадлежности к NPH===
| |
| − | Сведем задачу о выполнимости булевых формул вида 3-КНФ (3CNF SAT) к HAM. Начнем построение экземпляра HAM по булевой формуле в 3КНФ. Пусть формула имеет вид <math>E = e_1 \land e_2 \land... \land e_k</math>, где каждое <math>e_i</math> - дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} + \alpha_{i2} + \alpha_{i3})</math>. Пусть <math>x_1, x_2, ..., x_n</math> - переменные в формуле <math>E</math>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунке 1.
| |
| − | | |
| − | Для каждой переменной <math>x_i</math> строится подграф <math>H_i</math>, структура которого показана на рис. 2. Здесь <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>.
| |
| − | | |
| − | ==Формулировка задачи о гамильтоновом пути в графе==
| |
| − | В '''задаче об (ориентированном) гамильтоновом пути в графе''' ([U]HAMP) в качестве входных данных выступает (ориентированный) граф <math>G</math>. Требуется выяснить, есть ли в заданном (ориентированном) графе <math>G</math> (ориентированный) гамильтонов путь.
| |
| − | | |
| − | ==Доказательство NP-полноты задачи об ориентированном гамильтоновом пути в графе (HAMP)==
| |
| − | Для доказательства того, что HAMP <math>\in</math> [[NPC]], необходимо доказать два факта:
| |
| − | *HAMP <math>\in</math> [[NP]]
| |
| − | *HAMP <math>\in</math> [[NPH]]
| |
| − | ===Доказательство принадлежности к NP===
| |
| − | В качестве сертификата возьмем ориентированный гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
| |
| − | ===Доказательство принадлежности к NPH===
| |
| − | Сведем задачу об ориентированном гамильтоновом цикле (HAM) к HAMP. Пусть дан граф <math>G</math>. Выберем произвольную вершину графа <math>G</math> и раздвоим ее, и входящие дуги направим в одну из полученных вершин, а исходящие пустим из другой. Теперь, если в исходном графе был ориентированный гамильтонов цикл, то в полученном будет ориентированный гамильтонов путь. В обратную сторону, если в полученном графе будет ориентированный гамильтонов путь, то на первом и последнем местах в этом пути окажутся новые вершины, соответствующие раздвоенной, поскольку ни одна из них не может оказаться в середине пути (у неё есть либо входящие, либо исходящие дуги). Таким образом, если в полученном графе будет гамильтонов путь, то в исходном графе <math>G</math> был гамильтонов цикл.
| |
| − | | |
| − | ==Доказательство NP-полноты задачи о гамильтоновом пути в графе (UHAMP)==
| |
| − | Для доказательства того, что UHAMP <math>\in</math> [[NPC]], необходимо доказать два факта:
| |
| − | *UHAMP <math>\in</math> [[NP]]
| |
| − | *UHAMP <math>\in</math> [[NPH]]
| |
| − | ===Доказательство принадлежности к NP===
| |
| − | В качестве сертификата возьмем гамильтонов путь в графе <math>G</math>. Очевидно, он удовлетворяет всем требованиям, налагаемым на сертификат. Проверяющая функция строится очевидным образом, работает за полиномиальное от размера входа время.
| |
| − | ===Доказательство принадлежности к NPH===
| |
| − | Сведем задачу о гамильтоновом цикле (HAMP) к UHAMP. Пусть дан ориентированный граф <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> будет ориентированный гамильтонов путь.
| |
