h1. Ciclu hamiltonian in graf dens
(Creat de '_fluffy_':user/fluffy la data de _2004-11-09_ categoria _Grafuri_, autor(i) _Crestez Leonard_)
(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(N^2^)$}.
h2. 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.
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 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.
Problema luata in discutie este propusa pe lista "sgu":http://acm.sgu.ru/, nr. 122, unde exista si evaluator online. Atentie la implementare! Citirea si scrierea folosind functii standard pot iesi din timp!
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(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://infoarena.ro/forum.
Problema luata in discutie este propusa pe lista "sgu":http://acm.sgu.ru/, nr. "122":http://acm.sgu.ru/problem.php?contest=0&problem=122, unde exista si evaluator online. Atentie la implementare! Citirea si scrierea folosind functii standard pot iesi din timp!
