infoarena

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

Si intrebarea este ....  :-s sau imi scapa mine ceva ?

Nu e intrebare, ci e o cerinta: .

:eyebrow: 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 :P

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 ?

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

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

nu

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

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

mah shi dar 1->2->3->4->->5->1 este el insushi ciclu de ce u nu zici ca e corect asha ??? :-k 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??

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

shtii ca asta e NP??

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

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

Daca tu vrei numarul de cicluri dintr-un graf neorientat poti sa faci matricea inchiderii tranzitive :D 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 :P
 ps: probleme Segments nu se rezolva cu grafuri. Trebuie sa determini punctul comun al mai multor drepte.

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

@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.
:peace:

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