Lanț - Grafuri neorientate

Lungimea unui lanț reprezintă numărul de muchii pe care acesta îl conține (numărul de noduri - 1).

Clasificarea lanțurilor în graful neorientat

1. În funcție de muchii:
• lanț simplu: toate muchiile din lanț sunt diferite între ele (nu se repetă nicio muchie);
• lanț compus: se pot repeta unele muchii de mai multe ori.

2. În funcție de noduri:
• lanț elementar: toate nodurile diferă 2 câte 2 (nu se trece prin același nod de 2 ori);
• lanț neelementar: se pot repeta nodurile (se poate trece prin același nod de 2 ori).

Exemple de lanțuri în graful neorientat:

Ce putem spune despre lanțurile din graf?

Toate lanțurile din graf sunt lanțuri simple. Apoi:
• L1 este lanț elementar de lungime 2;
• L2 este lanț elementar de lungime 4 (toate nodurile diferă);
• L3 este lanț elementar de lungime 6 (cel mai lung lanț elementar posibil, n-1 muchii);
• L4 este lanț neelementar de lungime 4 (se repetă nodul 5);
• L5 este lanț neelementar de lungime 9.

Dacă găsim un lanț între două noduri x și y, atunci putem găsi și un lanț elementar între x și y.

Știm că într-un lanț neelementar, un nod se repetă. Astfel, apare un fel de buclă (un Un ciclu în interiorul unui lanț.subciclu) care poate evitată.
În exemplul nostru, bucla se formează la nodul 7. Evitând nodurile 3 și 2, putem obține un lanț elementar.