Clarificare de termeni in teoria grafurilor + o probl. interesanta

[•arvlge]

Vreau sa stiu daca bucla este un termen existent in teoria grafurilor si daca inseamna ce cred eu ca inseamna adica o muchie de la un varf la el insusi.
Am nevoie de inf. asta pentru ca e vitala pentru rezolvarea unei probleme: Cate grafuri neorientate distincte fara bucle cu 4 noduri exista?Doua grafuri sunt considerate distincte daca difera prin matricile de adiacenta.
Daca bucle inseamna ce cred eu ca inseamna atunci raspunsul e 2 la 6.
Daca prin bucle problema se refera la cicluri, de exemplu, atunci "am ajuns la concluzia" ca ar trebui sa fie 38. Prin "am ajuns la concluzia" inteleg am tot desenat grafuri pana am cazut .
Dar serios acuma: precizarea "Doua grafuri sunt considerate distincte daca difera prin matricile de adiacenta" m-a ajutat sa-mi dau seama ca atunci cand vine vorba de un graf cu doua muchii, de exemplu, am 15 grafuri diferite (deorece luand un fel de graf reprezentant si rotindu-l considerand nodurile stationare[adica doar muchiile se misca]iti ies toate grafurile).
Daca vreti un exemplu mai clar: hai sa spunem ca nodurile sunt aranjate ca si colturile unui patrat si avem doua muchii aranjate ca una dintre cele doua perechi de laturi paralele. Daca consideram colturile(nodurile) stationare si rotim doar laturile(muchiile) cu 90 de grade atunci obtinem celelalte doua laturi paralele, dar graful e diferit fata de cel dinainte deoarece alte noduri sunt conectate cu acele muchii.
Facand asta si pentru 3 muchii avem inca 16 grafuri.Graf fara nicio muchie avem doar unul, cu o muchie avem 6 si in total avem 38(de la 4 muchii incepi sa ai cicluri indiferent de cum le aranjezi).
As vrea sa stiu daca la aceasta problema(cea cu cicluri) raspunsul e corect(apropo problema nu vine si cu raspuns, de aia nu stiu ce intelege problema prin "bucla").
Ca sa avem o scurta recapitulare:
-ce e aia bucla?
-daca in loc de "bucla" avem "ciclu" problema e rezolvata corect?
-daca raspunsul la prob. dinainte e corect/incorect, atunci exista modalitati mai eficiente de rezolvare(formule,algoritmi etc.)/modaltitati de rezv.?
Daca vreti sa rezv. problema cu cicluri atunci va urez mult succes!!!

[•klamathix]

Probabil că buclă înseamnă ce crezi tu, termenul în engleză e mai explicit "self-loop". În general mi se pare indicat ca termenii de genul ăsta să fie explicați. Nu există o terminologie consacrată.

Pare corect ce zici pentru numărul de grafuri fără cicluri. Se poate calcula numărul ăsta pentru un număr de noduri mai mare în timp bun astfel:

- Dacă nu are cicluri, graful este o mulțime de componente conexe, fiecare fiind un arbore ("o pădure").
- Numărul de arbori etichetați cu N noduri are formulă, care poate fi dedusă cu: https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
- Poți face programare dinamică cu o stare de genul: nr[ i][j] = câte grafuri pot construi din i noduri partiționate în j arbori? Recurența va simula adăugarea unui nou arbore, cu niște coeficienți care semnifică alegerea nodurilor care vor forma noul arbore și formula de mai sus pentru a număra structurile posibile ale noului arbore.