Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2004-11-09 00:00:00.
Revizia anterioară   Revizia următoare  

Ciclu hamiltonian in graf dens

(Creat de fluffy la data de 2004-11-09 categoria Grafuri, autor(i) Crestez Leonard)

Continut scurt:

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

In acest articol va voi prezenta un algoritm ce necesita O(n^2) timp de executie pentru gasirea unui ciclu hamiltonian intr-un graf neorientat dens - in care fiecare nod are macar (n + 1) / 2 muchii incidente.

Continut lung:

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

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

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 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 [1]forum.

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

References

Visible links
1. http://info.devnet.ro/forum.php
2. http://acm.sgu.ru/