97
правок
Изменения
м
{{Определение
|definition = '''(Ориентированным) гамильтоновым путем''' в (ориентированном) графе <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>.
}}
{{Определение
|definition = '''(Ориентированным) гамильтоновым циклом''' в (ориентированном) графе <math>G</math> называется гамильтонов путь <math>n_{1}</math>, <math>n_{2}</math>, ..., <math>n_{k}</math> такой, что существует ребро из <math>n_{k}</math> в <math>n_{1}</math>.
}}
интервики на гамильтонов граф
==Задача о гамильтоновом цикле в графе==
{{Определение
|definition = '''[U]HAM''' - задача нахождения (ориентированного) [[Гамильтоновы графы#Основные определения|гамильтонова цикла ]] в заданном графе.
}}
===Доказательство NP-полноты для неориентированного графа===
==Задача о гамильтоновом пути в графе==
{{Определение
|definition = '''[U]HAMP''' - задача нахождения (ориентированного) [[Гамильтоновы графы#Основные определения|гамильтонова пути ]] в заданном графе.
}}
