Ciclu - Grafuri neorientate
Fie un graf neorientat.
Se numește ciclu în graful un lanț simplu în care primul nod coincide cu ultimul nod.
Înțelegem astfel că un ciclu este de fapt un lanț care pleacă și ajunge în același vârf.
Clasificarea ciclurilor
Ciclurile în graful neorientat se clasifică astfel:
- ciclu elementar : nodurile sunt distincte, nu se repetă (cu excepția extremităților);
- ciclu neelementar : nodurile se pot repeta.
Exemple de cicluri elementare și neelementare:
Interpretând exemplul, observăm că:
- C1 este ciclu elementar de lungime 3;
- C2 este cel mai lung ciclu elementar din graf, de lungime 4;
- C3 este ciclu neelementar (se repetă în interior nodul 3);
- C4 și C5 sunt cicluri neelementare de lungime 6.
Numim graf aciclic un graf care nu conține cicluri. Într-un graf aciclic, orice lanț simplu este lanț elementar.