Grafuri-Drumuri si circuite
Lanț. Drum. Circuit
DEFINIȚIE 1: Se numeşte lanţ într-un graf neorientat, o secvenţă de noduri L=[x1, x2, ..., xk], unde x1, x2, ..., xkÎX,, cu proprietatea că oricare două noduri consecutive din secvenţă sunt adiacente( muchiile[x1, x2], [x2, x3], ..., [xk-1, xk]ÎU - adică există muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] în graful G). Nodurile x1 şi xk se numesc extremităţile lanţului, iar numărul muchiilor care intră în componenţa lanţului reprezintă lungimea lanţului.
DEFINIȚIA 2: Un lanţ este elementar dacă el nu conţine de mai multe ori acelaşi vârf.
DEFINIȚIA 3: Un lanţ este simplu dacă el nu conţine de mai multe ori aceeaşi muchie.
DEFINIȚIA 4: Se numeşte ciclu un lanţ simplu pentru care extremitatea iniţială coincide cu extremitatea finală.
DEFINIȚIA 5: Ciclul se numeşte elementar dacă nu conţine de mai multe ori acelaşi vârf (exceptând extremităţile sale).
Exemplu:Pentru graful de mai sus
1, 2, 4, 3, 5 este lanţ elementar, de lungime 4
3, 5, 1, 3 este lanţ neelementar de lungime 3( nodul 3 se repetă)
2, 4, 3, 1, 2 este circuit elementar de lungime 4