LANT.CICLU N.B.

LANT

            Se numeste lant o succesiune de noduri x₁ ... x_k, cu proprietatea ca oricare doua noduri vecine (x_i,x_i+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.

x₁, x_k 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.

G1:	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
G2:	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

Lant hamiltonian = un lant elementar care contine toate nodurile unui graf

L=[2 ,1, 6, 5, 4, 3] este lant hamiltonian

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

CICLU

Se numeste ciclu intr-un graf neorientat un lant x₁,x₂ ... x_k si oricare 2 muchii (x_i,x_i+1) sunt distincte.

Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.

G2:	1,2,3,4,1 - Ciclu elementar 2,3,4,1,2 - Ciclu elementar 1,2,3,4,2,3,1 - Nu este ciclu 1,2,3,4,2,5,1 - Ciclu neelementar

Ciclu hamiltonian = un ciclu elementar care contine toate nodurile grafului

C=[1,2,3,4,5,6,1] este ciclu hamiltonian

Ciclu eulerian = un ciclu simplu care contine toate muchiile grafului

C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian

Conditii necesare si suficiente

 Fie un graf conex fara noduri izolate cu n≥ 3 noduri. Daca pentru oricare nod al sau, x, d(x) este par atunci graful este eulerian.

Daca G este un graf cu n>=3 noduri astfel incat gradul fiecarui nod este mai mare sau egal decat n/2 atunci G este hamiltonian.