Гамильтонов цикл: различия между версиями

Гамильтонов цикл (посмотреть исходный код)

33 байта добавлено , 8 октября 2009

нет описания правки

4624

правки

@@ Строка 1: / Строка 1: @@
 '''Гамильтонов цикл''' - (''[[Hamiltonian circuit]]'') - ''[[цикл]]'' в [[граф|графе]], проходящий через каждую [[вершина|вершину]] в точности один раз.
-Задача выяснения, имеет ли данный граф гамильтонов цикл, является <math>NP</math>-''полной'', причем как в классе [[неориентированный граф|неориентированных]], так и [[ориентированный граф|ориентированных графов]].
+Задача выяснения, имеет ли данный граф гамильтонов цикл, является [[NP-Полная задача|<math>NP</math>-''полной'']], причем как в классе [[неориентированный граф|неориентированных]], так и [[ориентированный граф|ориентированных графов]].
 ==Литература==
 [Зыков/69],
 [Лекции]