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

Версия от 12:21, 8 октября 2009

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

Задача выяснения, имеет ли данный граф гамильтонов цикл, является NP-полной, причем как в классе неориентированных, так и ориентированных графов.

[Зыков/69],

[Лекции]

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