Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Ciclu hamiltonian in graf dens  (Citit de 7391 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 02:51:41 »

Comentarii la articolul Ciclu hamiltonian in graf dens
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Sorin_Ionut
Client obisnuit
**

Karma: 14
Deconectat Deconectat

Mesaje: 53



Vezi Profilul
« Răspunde #1 : Martie 05, 2009, 21:11:10 »

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 ....  Brick wall Brick wall Brick wall

Multumesc anticipat !
 B.Y.S.
Memorat
unudoitrei
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #2 : Aprilie 16, 2013, 07:52:53 »

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.
Memorat
CosminRusu
De-al casei
***

Karma: 77
Deconectat Deconectat

Mesaje: 104



Vezi Profilul
« Răspunde #3 : Decembrie 03, 2013, 09:23:54 »

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!
Memorat
AlexandruValeanu
Vorbaret
****

Karma: 29
Deconectat Deconectat

Mesaje: 167



Vezi Profilul
« Răspunde #4 : Decembrie 03, 2013, 19:47:34 »

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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines