O Problema do Ciclo Hamiltoniano (HC) consiste em encontrar um ciclo que atravessa todos os vértices em um determinado gráfico não direcionado. O Travelling Salesman Problem (TSP) consiste em encontrar um ciclo que atravesse todos os vértices em um determinado gráfico ponderado pelas arestas e minimize a distância total medida pela soma dos pesos das arestas no ciclo. HC é um caso especial de TSP, e ambos são conhecidos por serem NP-completos [Garey & Johnson]. (Consulte os links acima para obter mais detalhes e variantes desses problemas.)
Existem classes de gráficos estudadas nas quais o Problema do Ciclo Hamiltoniano é solucionável em tempo polinomial por meio de um algoritmo não trivial , mas o Problema do Vendedor Viajante é difícil para NP?
Não trivial é excluir classes como a classe de gráficos completos, onde é garantido que existe um ciclo hamiltoniano e pode ser encontrado com facilidade, ou geralmente classes de gráficos em que é garantido que sempre existe um HC.
fonte
Que tal gráficos completos ? Como o TSP sempre pode ser reduzido a uma instância em gráficos completos (adicionando distâncias adequadas entre não arestas), ainda é difícil para o NP resolver o TSP em gráficos completos. Mas qualquer gráfico completo é hamiltoniano.
fonte
Existem muitas classes infinitas de gráficos que são conhecidos por possuir circuitos hamiltonianos. Duas classes especialmente interessantes são os n-cubos e os gráficos de Halin. Uma maneira de pensar nos gráficos de Halin é incorporar uma árvore com pelo menos 3 vértices e que não tenha vértices de valência dois no plano e depois passar um circuito simples pelos vértices 1 valentes da árvore.
http://en.wikipedia.org/wiki/Halin_graph
Sabe-se que esses gráficos têm um HC e, na verdade, são pancíclicos (circuitos de todos os comprimentos) ou não possuem exatamente um comprimento de circuito que deve ter comprimento uniforme.
fonte