4.3.6. Otros problemas con grafos.
Problema del ciclo hamiltoniano
Dado un grafo no dirigido G, un ciclo hamiltoniano es un ciclo simple que visita todos los vértices.
Problema del ciclo hamiltoniano.
Determinar si un grafo no dirigido dado tiene un ciclo hamiltoniano.
Aunque el problema es muy parecido al del circuito de Euler, no se conoce ningún algoritmo eficiente para resolverlo, en tiempo polinomial.
El problema del ciclo hamiltoniano pertenece a un conjunto de problemas de difícil solución llamado problemas NP-completos.
La solución requiere básicamente evaluar todas las posibilidades, dando lugar a un orden de complejidad exponencial o factorial.
Otra posibilidad es usar métodos heurísticos, que pueden funcionar en algunos casos y en otros no.