Ciclu hamiltonian in graf dens

(Categoria Algoritmi, Autor Leonard Crestez)

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(N2).

Algoritm

La inceput formam un ciclu la intamplare, fara a tine cont daca muchiile luate in considerare chiar exista in graf. Astfel, putem alege chiar ciclul 1, 2, 3, 4, ... N. Daca acest ciclu este valid, atunci avem noroc si solutia a fost gasita. Altfel, trebuie sa incercam sa "umplem gaurile" din ciclu (adica muchiile pe care le-am ales la intamplare si care nu exista in graf).

Gasim prima muchie de acest fel, fie ea (A, B). Cautam apoi doua alte noduri adiacente in ciclul nostru, notate cu C si D, astfel incat sa avem muchie de la A la C si de la B la D. Se poate demonstra ca vom gasi mereu C si D. Acum vom "incrucisa" A B cu C D. Prin "incrucisare" se intelege transfromarea unui ciclu ...AB...CD... in ...AC...BD... (sau ...CD...AB... in ...CA...DB...) . Atentie, secventa de la B la C (respectiv de la D la A) va fi inversata complet!

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 nodurilor AB, CD, si incrucisare. Avand in vedere ca sunt maxim N gauri la inceput, algoritmul necesita O(N2) 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.

Problema luata in discutie este propusa pe lista sgu, nr. 122, unde exista si evaluator online. Atentie la implementare! Citirea si scrierea folosind functii standard pot iesi din timp!

remote content