CONEXITATE  IN GRAFURI

Def:  Fie graful G=(X, U). Numim lant o succesiune de varfuri L = {x₁, x₂, …, x_p} cu propietatea ca oricare doua varfuri succesive sunt adiacente, adica [x₁, x₂] Î U, [x₂, x₃] Î U, …, [x_p-1, x_p] Î U.

Varfurile x₁ si x_p  se numesc extremitatile lantului, iar numarul de muchii ce il compun se numeste lungimea lantului.

Def: Daca varfurile x₁, x₂, …, x_p sunt distincte doua cate doua, lantul  se numeste lant elementar. In caz contrar lantul se numeste neelementar.

Def: Daca intr-un lant, toate muchiile sunt diferite intre ele, lantul se numeste simplu, in caz contrar lantul se numeste compus.

Def:  Daca varfurile x₁ si x_p coincid lantul se numeste ciclu.

Daca un ciclu are o lungime para, el se numeste par, altfel impar

Def: Daca intr-un ciclu, toate varfurile sunt distincte intre ele, cu exceptia primului si ultimului atunci ciclul se numeste ciclu elementar.

Def: Un graf se numeste conex daca oricare ar fi doua varfuri x si y, exista un lant ce le leaga.

Def: Fie graful G=(X, U). Un subgraf C = (X₁, U₁) al sau conex se numeste componenta conexa a grafului G daca are in plus propietatea ca nu exista nici un lant in G sa lege un varf din X₁ cu un nod din X – X₁.

Teorema: Componentele conexe X_i ale unui graf genereaza o partitie a lui X, adica multimile X_i au propietatile:

                1. X_i ¹ Æ,  pentru orice i Î N

                2. X_i ¹ X_j  Þ  X_i Ç X_j = Æ , pentru orice i Î N

                3. reuniunea lor este chiar X

Teorema:  Un graf este conex numai si numai daca are o singura componenta conexa.

Def:  Fie graful G=(X, U). Daca exista varfuri intre care exista mai mult de o muchie, graful este numit multigraf.

Def: Fie graful G=(X, U). Daca exista un lant elementar care contine toate varfurile grafului, lantul se numeste lant hamiltonian.

Def:  Daca intr-un lant hamiltonian varful initial si varful final coincid lantul se numeste ciclu hamiltonian iar despre graf spunem ca se numeste graf hamiltonian

Teorema:  K_n (graful complet) este un graf hamiltonian

Def: Fie graful G=(X, U). Daca exista un lant care contine toate muchiile grafului o singura data fiecare, lantul se numeste lant eulerian.

Def:  Daca intr-un lant eulerian varful initial si varful final coincid lantul se numeste ciclu eulerian iar despre graf spunem ca se numeste graf eulerian

Teorema:  Un graf G fara varfuri izolate este eulerian daca si numai daca este conex si gradul fiecarui varf este par.