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>]]
Причина в том, что если цикл переходит из <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>]]
