Grafuri Hamiltoniene

Sunt grafurile ce conțin un traseu (ciclu) care vizitează toate nodurile și care revine în nodul de pornire fără a trece printr-un nod de două ori (traseu numit ciclu hamiltonian).

Problema determinării ciclului hamiltonian este una NP-completă (NP = non polynomial) în cazul unui graf oarecare.

Aici prezentăm doi algoritmi: backtracking (pe cazul general), și un algoritm polinomial, care însă funcționează doar pe un tip special de graf, cu multe muchii, numit graf dens.

Pentru acești algoritmi considerăm că grafurile au muchiile neetichetate (fără costuri).

Pentru grafuri în care muchiile au cost asociat există un aloritm bazat pe programare dinamică pentru găsirea unui ciclu hamiltonian de cost minim. Acesta va fi prezentat ulterior ca aplicație a programării dinamice pe stări exponențiale.