Ciclu

  Fie G=(X,U) un graf neorientat.

Se numește ciclu în graful G un lanț simpluLanțul simplu este un lanț în care nu se repetă nicio muchie. în care primul nod coincide cu ultimul nod.

Denumim ciclu elementar un ciclu în care nodurile sunt distincte 2 câte 2, cu excepția primului și ultimului nod (extremitățile).

Graf neorientat + Cicluri
    Din figură:
  • C3 este cel mai lung ciclu (neelementar);
  • C1 și C2 sunt cicluri elementare;
  • C4 și C5 au aceeași lungime, 6 (lungimea este dată de numărul de muchii);
  • C2 este cel mai lung ciclu elementar;

Numim graf aciclic un graf care nu conține cicluri. Într-un graf aciclic, orice lanț simplu este lanț elementarLanțul elementar este un lanț în care nodurile diferă două câte două..