De ce contează?
Un turist are de vizitat fiecare oraș de pe o hartă, dar nu vrea să piardă timp: fiecare oraș exact o dată, fără să treacă de două ori prin același loc, iar la final să se întoarcă acasă, în orașul din care a plecat. Întrebarea pare simplă, dar e una dintre cele mai grele din toată informatica: există un asemenea traseu?
Ce este
Imaginează-ți orașele ca noduri și șoselele dintre ele ca muchii. Turistul vrea un traseu închis care atinge fiecare nod o singură dată și se închide unde a început. Nu îl interesează șoselele în sine — poate lăsa oricâte nefolosite — ci faptul că trece prin toate locurile fără să repete vreunul.
Formal, pentru un graf cu n noduri:
- Ciclu hamiltonian = un ciclu care trece prin toate nodurile grafului
exact o dată și revine la nodul de plecare. (Lungimea lui este mereu
nmuchii, fiindcă atinge fiecare dintre celennoduri o singură dată.) - Graf hamiltonian = un graf care admite cel puțin un ciclu hamiltonian.