Lanţ

Definiţie 1.2.3.1 Fie un graf neorientat G=(X, U). Se numeşte lanţ al grafului G o succesiune de noduri L=[x1, x2, ..., xk], unde x1, x2, ..., xkÎX, cu proprietatea că [x1, x2], [x2, x3], ..., [xk-1, xk]ÎU (adică există muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] în graful G).

Definiţe 1.2.3.2 Fie un graf neorientat G=(X, U) ş L=[x1, x2, ..., xk] un lanţal grafului G. x1 şi xk se numesc extremităţle lanţlui, iar număul muchiilor care intră în componenţa lanţului reprezintă lungimealanţului.

Exemplu: Pentru graful din figura 1.19 se pot distinge mai multe lanţuri printre care

L1=[1, 2, 3, 5, 4, 8], L2=[1, 2, 3, 2], L3=[9, 3, 5, 4, 3, 2], L4=[6, 7, 3, 5, 4, 8]

 

Figura 1.19

Definiţie 1.2.3.3 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă nodurile x1, x2, ..., xk sunt distincte două câte două, atunci lanţul se numeşte elementar. În caz contrar lanţul se numeşte ne-elementar.

Exemplu: Lanţurile L1 şi L4 din exemplul anterior sunt elementare. Lanţurile L2 şi L3 din exemplul anterior sunt ne-elementare.

Definiţie 1.2.3.4 Fie un graf neorientat G=(X, U) şi L=[x1, x2, ..., xk] un lanţ al grafului G. Dacă muchiile [x1, x2], [x2, x3], ..., [xk-1, xk] sunt distincte două câte două, atunci lanţul se numeşte simplu. În caz contrar lanţul se numeşte compus.

Exemplu: Lanţurile L1, L3, L4 din exemplul anterior sunt simple. Lanţul L2 din exemplul anterior este compus.

Observaţie: Orice lanţ elementar este simplu. Reciproca nu este valabilă (se poate întâmpla ca lanţul să fie simplu, dar să fie ne-elementar – vezi lanţul L3 din exemplul lanţurilor).