Grafuri Hamiltoniene

Acestea sunt grafurile ce permit obținetea un traseu care să viziteze toate nodurile și care să revină în nodul de pornire fără a trece printr-un nod de două ori (traseu numit ciclu hamiltonian).

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

Aici prezentăm doi algoritmi: backtracking (pe cazul general), și un algoritm polynomial, 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.