Réduction du cycle hamiltonien simple

Question

Hampathe

• Saisir: Un graphique non dirigé $ G $ et 2 nœuds $ s, t $

• Question: G contient-il un chemin hamiltonien de $ s $ à $ t $?

Hamcycle

• Saisir: Un graphique non dirigé $ G $ Et un nœud $ s $

• Question: Fait $ G $ contenir un cycle hamiltonien à partir de $ s $?

Je souhaite montrer que HamCycle est NP-Dury. Je vais montrer ça en faisant $ Hampath leq_p hamcycle $ Puisque Hampath est connu pour être NP-Complete.

---

Ajouter le bord de t à s

S'il y a un hampath, la réduction montre qu'il y a un hamcycle

Si il y a un hamcycle, il y a clairement un hampath

---

Ci-dessus est toute ma tentative. Je me demandais si je pouvais appeler $ t $ Dans ma réduction car il n'est pas utilisé comme entrée dans Hamcycle?