Cycle hamiltonien, vérifiant et trouver

Question

Si nous avons un algorithme qui, en temps polynomial, indique si un graphone G a un cycle hamiltonien, pouvons-nous avoir un algorithme qui en temps polynôme trouver un cycle hamiltonien?

Ma tentative est de supprimer un bord de graphique G et d'avoir g ', après avoir exécuté l'algorithme sur G' pour savoir s'il a un cycle hamiltonien, sinon cela signifie que le bord est dans un cycle hamiltonien.Maintenant, je ne sais pas comment continuer.

Answer 1

let $ p $ soit un chemin simple arbitraire dans le graphique. Si $ p $ apparaît dans un cycle hamiltonien du graphique, vous pouvez supprimer tous les sommets de $ p $ Sauf le premier et le dernier sommet, connectez ces deux sommets avec un bord et le graphique résultant doit être hamiltonien.

Garder cela à l'esprit, nous pouvons construire le cycle hamiltonien étape par étape en commençant par le chemin de la longueur, car vous avez déjà décrit comment construire un tel chemin. Ensuite, nous pouvons étendre un chemin de longueur $ i $ à un chemin de longueur $ i + 1 $ en utilisant L'astuce ci-dessus, où nous essayons tous les voisins du dernier sommet dans le chemin d'un prochain sommet et nous appliquons l'astuce ci-dessus pour vérifier si un cycle hamiltonien existe là où le nouveau chemin fait partie du cycle. Notez que nous appelons la boîte noire au plus $ m:= | e | $ fois. Une fois que nous atteindrons un chemin de longueur $ N-3 $ Il est facile de terminer le chemin dans un cycle hamiltonien en temps linéaire.