infoarena

Comentarii la articolul Ciclu hamiltonian in graf dens (http://infoarena.ro/ciclu-hamiltonian-in-graf-dens)

Salutare !
Am si eu o nelamurire la acest algoritm.

Sa luam de exemplu graful reprezentat prin
6 noduri si 10 muchii
1 2
1 3
1 6
2 3
2 4
2 5
3 6
4 5
4 6
5 6
gradul nod : 1 = 3
                 2 = 4
                 3 = 3
                 4 = 3
                 5 = 3
                 6 = 4
Deci gradele sunt mai mari de (6+1)/2=3

Fie ciclul presupus corect la ineceput 1 2 3 4 5 6 1
Pas 1) Exista muchie de la 1->2 ? (DA)
Pas 2) Exista muchie de le 2->3 ? (DA)
Pas 3) Exista muchie de la 3->4 ? (NU)
i) Cauta 2 noduri ai sa am muchie de la 3->x si de la 4->y
ii) Gasesc pe x ca fiind 6 si y ca 5

/////////// aici nu stiu daca procedez bine daca gresesc corectati-ma !!!

iii) Incrucisez si obtin 3->6->5->4
---) Concluzie am gasit pana la acest pas lantul 1->2->3->6->5->4
Pas 4) Cum nu mai am de adaugat decat nodul 1 pt ca algoritmul sa-mi genereze un ciclu hamilonian dau de o problema
 Nu am muchie de la 4->1 (ups !!!)

Nu am inteles eu bine ?, Va rog mult si cu respect spuneti-mi si mie unde gresesc ....  ](*,) ](*,) ](*,)

Multumesc anticipat !
 B.Y.S.

Atunci cand iei nodurile C si D, incearca sa iei drept nodul C pe 1 si drept nodul D pe 2, dupa "acoperirea gaurii" vei avea lantul 1->3->2->4->5->6->1.

Am si eu cateva nelamuriri. Am citit dintr-o carte a doamnei Cerchez despre ciclul hamiltonian in graf turneu. Graful turneu e la grafuri orientate, iar la cele neorientate e graf dens? Daca nu, care e diferenta dintre cele doua notiuni?
Tot in cartea respectiva am gasit un algoritm diferit de cel propus in acest articol. Acolo ideea e sa extindem prima data ciclul la stanga, la dreapta si mai apoi sa inseram cate un nod in ciclul actual.
Multumesc anticipat!

Graful turneu este un graf orientat ce se obtine dintr-un graf complet neorientat, caruia i se atribuie o directie pentru fiecare muchie. Graful dens poate fi atat neorientat cat si orientat si presupune doar un graf cu un numar de muchii cat mai apropiat de numarul maxim de muchii posibile.