- Se numeste ciclu intr-un graf neorientat un lant x1,x2 ... xk si oricare 2 muchii (xi,xi+1) sunt distincte.
- Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.
Exemple:
![Picture](/uploads/2/8/6/9/28694867/1468534.png)
1,2,3,4,1 - Ciclu elementar
2,3,4,1,2 - Ciclu elementar
1,2,3,4,2,3,1 - Nu este ciclu
1,2,3,4,2,5,1 - Ciclu neelementar
2,3,4,1,2 - Ciclu elementar
1,2,3,4,2,3,1 - Nu este ciclu
1,2,3,4,2,5,1 - Ciclu neelementar
Cicluri particulare
![Picture](/uploads/2/8/6/9/28694867/5633993.png)
Ciclu hamiltonian = un ciclu elementar care contine toate nodurile grafului
C=[1,2,3,4,5,6,1] este ciclu hamiltonian
C=[1,2,3,4,5,6,1] este ciclu hamiltonian
![Picture](/uploads/2/8/6/9/28694867/943933.png)
Ciclu eulerian = un ciclu simplu care contine toate muchiile grafului
C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian
C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian
Conditii necesare si suficiente:
Fie un graf conex fara noduri izolate cu n≥ 3 noduri. Daca pentru oricare nod al sau, x, d(x) este par atunci graful este eulerian.Daca G este un graf cu n>=3 noduri astfel incat gradul fiecarui nod este mai mare sau egal decat n/2 atunci G este hamiltonian.
Fie un graf conex fara noduri izolate cu n≥ 3 noduri. Daca pentru oricare nod al sau, x, d(x) este par atunci graful este eulerian.Daca G este un graf cu n>=3 noduri astfel incat gradul fiecarui nod este mai mare sau egal decat n/2 atunci G este hamiltonian.