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

Версия от 13:40, 8 октября 2009

Гамильтонов цикл - (Hamiltonian circuit) - цикл в графе, проходящий через каждую вершину в точности один раз.

Задача выяснения, имеет ли данный граф гамильтонов цикл, является [math]\displaystyle{ NP }[/math]-полной, причем как в классе неориентированных, так и ориентированных графов.

[Зыков/69],

[Лекции]

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