numar minim de cicluri in graf

[•yonatan]

se da un graf neorientat, sa se determine un numar minim de cicluri care sa contzina( toate laolata) toate nodurile grafului
- avem voie sa avem 1 nod in mai multe cicluri

[•alexandru92]

Si intrebarea este ....  sau imi scapa mine ceva ?

[•gabitzish1]

Nu e intrebare, ci e o cerinta:

sa se determine un numar minim de cicluri care sa contzina( toate laolata) toate nodurile grafului

.

[•alexandru92]

Nu e intrebare, ci e o cerinta:

sa se determine un numar minim de cicluri care sa contzina( toate laolata) toate nodurile grafului

.

eu ma referam la ce vrea el sa facem ? sa-i dam idei de rezolvare, a propus o problema si vrea sa o rezolvam .... exista mai multe posibilitat

[•toni2007]

Nu e intrebare, ci e o cerinta:

sa se determine un numar minim de cicluri care sa contzina( toate laolata) toate nodurile grafului

.

eu ma referam la ce vrea el sa facem ? sa-i dam idei de rezolvare, a propus o problema si vrea sa o rezolvam .... exista mai multe posibilitat

Tu ce crezi ? Ti se pare ca un om care s-a inscris pe infoarena pentru a posta problema asta a facut-o doar de dragul de a pune o problema ?

[•pauldb]

Ai voie sa ai un nod de mai multe ori intr-un ciclu?

[•gabitzish1]

Cum poti avea un nod de mai multe ori intr'un ciclu? Nu inseamna ca ai mai multe cicluri acolo?

[•yonatan]

Cum poti avea un nod de mai multe ori intr'un ciclu? Nu inseamna ca ai mai multe cicluri acolo?

nu  un nod de mai multe ori intr-un ciclu ci un nod in mai multe cicluri diferite am o poza care v-ar lamuri ce vreau io dar din pacate nush cum sa o inserez

[•yonatan]

Ai voie sa ai un nod de mai multe ori intr-un ciclu?

nu

[•yonatan]

Nu e intrebare, ci e o cerinta:

sa se determine un numar minim de cicluri care sa contzina( toate laolata) toate nodurile grafului

.

eu ma referam la ce vrea el sa facem ? sa-i dam idei de rezolvare, a propus o problema si vrea sa o rezolvam .... exista mai multe posibilitat

sa-mi datzi o idee de rezolvare pentru cerintza de mai sus

[•yonatan]

http://a.imagehost.org/download/0038/graf

avetzi aici un exemplu pentru ce vreau eu cu roshu sunt muchiile  cu verde shi violet cele 2 cicluri
!nota am incercuit cu verde nodurile 2 shi 5 pentru a arata ca in locul ciclului violet putem avea ciclul 1->3->4->5->1 eliminandu-l pe 2 care ar fi de asemenea o solutzie buna de fapt nu se cer ciclurile ci numarul lor

[•APOCALYPTO]

mah shi dar 1->2->3->4->->5->1 este el insushi ciclu de ce u nu zici ca e corect asha sigur nu ai uitat ceva?? sau ai greshit exemplul??

[•yonatan]

mah shi dar 1->2->3->4->->5->1 este el insushi ciclu de ce u nu zici ca e corect asha sigur nu ai uitat ceva?? sau ai greshit exemplul??

aoleu  da pai fiecare nod dintr-un ciclu trebuie sa aiba cel putzin o muchie catre toate celelalte noduri din ciclu  vai de capul meu

[•APOCALYPTO]

mah shi dar 1->2->3->4->->5->1 este el insushi ciclu de ce u nu zici ca e corect asha sigur nu ai uitat ceva?? sau ai greshit exemplul??

aoleu   da pai fiecare nod dintr-un ciclu trebuie sa aiba cel putzin o muchie catre toate celelalte noduri din ciclu   vai de capul meu

asta nu inseamna ca tu de fapt cautai nishte clici shi nu nishte clici??

[•pauldb]

@yonatan: Nu posta consecutiv. Editeaza-ti mesajele anterioare.
In plus, cred ca exemplul dat de tine e gresit.
Mi-ar fi de folos daca ai posta cerinta completa a problemei din locul unde ai intalnit-o.

[•APOCALYPTO]

shtii ca asta e NP??

[•yonatan]

@yonatan: Nu posta consecutiv. Editeaza-ti mesajele anterioare.
In plus, cred ca exemplul dat de tine e gresit.
Mi-ar fi de folos daca ai posta cerinta completa a problemei din locul unde ai intalnit-o.

http://www.spoj.pl/problems/SEGMENTS/ dar nu e vorba despre un graf ci asa am facut eu transformare  fiecare linie orizontala am zis ca e un nod iar  intre 2 noduri exista muchie daca liniile orizontale respective pot fi unite cu o linie verticala

[•APOCALYPTO]

mah dar ce ar fi daca ai incerca ideea urmatoare
numar_de_clici=0
seteaza toate nodurile ca fiind nemarcate;
lista clique-goala;
cat timp (raman noduri nemarcate)
  {alege nod nemarcat shi introdu-l in lista clique;
  numar_de_clici++;
  cat timp (gaseshti nod nemarcat care de la care exista muchii catre toate nodurile din clique)
       {introdu-l in lista clique;
       marcheaza-l;
       }
  sterge toate elementele din lista clique;//ca sa o refoloseshti
  }
afiseaza numar_de_clici;
incearca sa faci un algoritm cu asta deshi nu itzi garantez ca merge

[•alexandru92]

Daca tu vrei numarul de cicluri dintr-un graf neorientat poti sa faci matricea inchiderii tranzitive http://infoarena.ro/problema/royfloyd. Daca gasesti pe diagonala principala valori de 1 inseamna ca acel varf apartine unui ciclu. Problema ce intervine este sa nu dai peste 2 varfuri care sunt din acelasi ciclu
 ps: probleme Segments nu se rezolva cu grafuri. Trebuie sa determini punctul comun al mai multor drepte.

[•wefgef]

Avem o sectiune a forumul dedicata problemelor de pe alte site-uri. Va recomand sa o folositi de acum incolo, in loc sa dati tot felul de interpretari mai mult sau mai putin corecte problemelor si sa le postati in "Informatica".

[•devilkind]

@alexandru92: Incearca sa te documentezi mai bine inainte sa dai un sfat.
Determinarea ciclurilor dintr-un graf neorientat (asa cum ai spus tu) este o binecunoscuta problema NP.
Determinarea numarului minim de cicluri care acopera un graf neorientat e o problema care are o solutie polinomiala (cel putin asa mi se pare mie) insa nu are nici o legatura cu algoritmul roy-floyd sau cu matricea inchiderii tranzitive.
De asemenea problema segments nu cere sa determini punctul comun al mai multor drepte.

[•yonatan]

ps: probleme Segments nu se rezolva cu grafuri. Trebuie sa determini punctul comun al mai multor drepte.

nu intzeleg la ce te referi in enuntz zice ca trebuie sa determini o linie care uneshte mai multe drepte. te rog sa explici daca eshti atat de sigur ca ii shtii rezolvarea