- Se numeste lant o succesiune de noduri x1 ... xk, cu proprietatea ca oricare doua noduri vecine (xi,xi+1) apartin de B.
- Un lanţ este simplu dacă nu trece de două sau mai multe ori prin aceeaşi muchie. În caz contrar el este lanţ compus.
- Un lanţ este elementar dacă trece o singură dată prin fiecare dintre vârfurile sale, în caz contrar numindu-se neelementar. x1, xk sunt extremitatile lantului.
- Lungimea lantului este egala cu numarul de muchii care il compun, k-1.
- Daca nodurile din lant sunt distincte, atunci lantul este elementar.
Exemple:
1,2,3,1,4 - Lant neelementar (lungime 4)
1,2,3,4 - Lant elementar (lungime 3)
1,2,3,1,2,5 - Lant neelementar (lungime 5)
1,2,3,5 - Nu este lant
1,2,3,4 - Lant elementar (lungime 3)
1,2,3,1,2,5 - Lant neelementar (lungime 5)
1,2,3,5 - Nu este lant
Succesiunea de varfuri 2, 3, 5, 6 reprezinta un lant simplu si elementar de lungime 3.
Lantul 5 3 4 5 6 este simplu dar nu este elementar.
Lantul 5 3 4 5 3 2 este compus si nu este elementar.
Lantul 3 4 5 3 reprezinta un ciclu elementar
Lantul 5 3 4 5 6 este simplu dar nu este elementar.
Lantul 5 3 4 5 3 2 este compus si nu este elementar.
Lantul 3 4 5 3 reprezinta un ciclu elementar
Lanturi particulare
Lant hamiltonian
Lant hamiltonian = un lant elementar care contine toate nodurile unui graf.
L=[2 ,1, 6, 5, 4, 3] este lant hamiltonian.
Lant hamiltonian = un lant elementar care contine toate nodurile unui graf.
L=[2 ,1, 6, 5, 4, 3] este lant hamiltonian.
Lant eulerian
Lant eulerian = un lant simplu care contine toate muchiile unui graf.
L=[1.2.3.4.5.3.6.2.5.6] este lant eulerian.
Lant eulerian = un lant simplu care contine toate muchiile unui graf.
L=[1.2.3.4.5.3.6.2.5.6] este lant eulerian.