De ce contează?
Ești un cavaler care trebuie să treacă prin fiecare oraș din regat exact o dată, mergând doar pe drumurile care există. Pleci dintr-un oraș, alegi un vecin nevizitat, apoi altul — și uneori te trezești într-un fund de sac, cu orașe rămase pe care nu le mai poți atinge de acolo. Nu renunți: te întorci pe ultimul drum și încerci altă ramificație. Exact așa cauți un lanț hamiltonian — încerci, te blochezi, dai înapoi, tai din start variantele care nu pot merge.
Intuiția
Un lanț hamiltonian trece prin fiecare nod exact o dată; dacă, în plus,
ultimul nod e legat de primul, ai un ciclu hamiltonian. Lecția-soră
graf-hamiltonian a definit noțiunea și a arătat de ce problema e grea — aici
ne interesează cum găsești efectiv un asemenea traseu.
Imaginea mentală: un DFS cu memorie care nu vizitează tot, ci caută un traseu care le atinge pe toate. Ții minte ce noduri ai pus în drum și mai adaugi unul doar dacă există muchie spre el și nu l-ai mai călcat. Când rămâi blocat, ștergi ultimul pas și încerci alt vecin.
Nu există niciun criteriu rapid care să decidă existența (problema e
NP-dificilă), deci cauți sistematic — dar nu orbește: tai devreme orice
ramură care nu mai poate continua. Iar la ciclu exploatezi simetria: un
ciclu trece prin toate nodurile, deci trece sigur și prin nodul 0 — poți
fixa startul în 0 și cauți o singură dată, nu de n ori.