In acest articol va voi prezenta un algoritm pentru gasirea unui ciclu hamiltonian intr-un graf neorientat dens - in care fiecare nod are macar $(N + 1) / 2$ muchii.

In general, gasirea unui ciclu hamiltonian intr-un graf neorientat este un exemplu clasic de problema NP - completa. Insa, daca graful este dens - fiecare nod are cel putin $(N+1) / 2$ muchii incidente ({$N$} este numarul de noduri) - se poate gasi o solutie de complexitate {$O(N^2)$}.

In general, gasirea unui ciclu hamiltonian intr-un graf neorientat este un exemplu clasic de problema NP - completa. Insa, daca graful este dens - fiecare nod are cel putin $(N+1) / 2$ muchii incidente ({$N$} este numarul de noduri) - se poate gasi o solutie de complexitate {$O(N^2^)$}.

h2. Algoritm

Se observa ca a scazut numarul de "gauri" din sir, $AB$ a fost eliminata si nu au fost adaugate "gauri" noi. Repetam "umplerea gaurilor" pana nu mai avem ce umple, deci am gasit solutie.

Desi suna complicat, "umplerea unei gauri" necesita doar $O(N)$ timp pentru cautarea nodurile {$AB$}, {$CD$}, si incrucisare. Avand in vedere ca sunt maxim $N$ gauri la inceput, algoritmul necesita $O(N^2)$ ca timp de executie.

Desi suna complicat, "umplerea unei gauri" necesita doar $O(N)$ timp pentru cautarea nodurile {$AB$}, {$CD$}, si incrucisare. Avand in vedere ca sunt maxim $N$ gauri la inceput, algoritmul necesita $O(N^2^)$ ca timp de executie.

Mai sus am folosit o afirmatie fara a o demonstra. Demonstratia e relativ intuitiva. Daca nu o descoperiti singuri, puteti sa intrebati pe "forum":http://info.devnet.ro/forum.php.