lanturi.cicluri.drumuri

Lanturi. Drumuri
A. Pentru grafuri neorientate
Se numeste lant o succesiune de noduri x1 ... xk, cu proprietatea ca oricare doua noduri vecine (xi,xi+1) apartin de B.
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.

B. Pentru grafuri orientate
Se numeste lant o succesiune de arce u1, u2 ... uk, cu proprietatea ca oricare doua arce de pe pozitii consecutive au un nod comun.
Observatie: nu conteaza ordinea de parcurgere
Se numeste drum o succesiune de noduri x1, x2 ... xk cu proprietatea ca (xi,xi+1) este arc.
Observatie: conteaza ordinea de parcurgere
Daca nodurile sunt distincte, drumul se numeste elementar

Cicluri. Circuite

A. Pentru grafuri neorientate
Se numeste ciclu intr-un graf neorientat un lant x1,x2 ... xk si oricare 2 muchii (xi,xi+1) sunt distincte.
Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.


B. Pentru grafuri orientate
Se numeste circuit intr-un graf un drum x1,x2 ... xk cu proprietatea ca x1 = xk si arcele (xi,xi+1) sa fie distincte 2 cate 2.
Un circuit in care toate nodurile sunt distincte cu exceptia capetelor se numeste circuit elementar.



Grafuri conexe
Un graf este conex daca este format dintr-un singur nod sau daca intre oricare doua noduri ale sale exista cel putin un lant.


Se numeste componenta conexa a unui graf un sungraf al sau care este conex si care este maximal in raport cu aceasta proprietate (daca i se adauga un nod isi pierde aceasta proprietate).
Observatie: pentru grafurile orientate nu se tine cont de orientarea arcelor.

Grafuri tare conexe
Un graf este tare conex daca ar un singur nod sau daca oricare ar fi (x,y) exista drum de la x la y si exista drum de la y la x.
Determinarea componentelor tare conexe
Se poate realiza prin 3 metode:
Utilizand metoda DF/BF
Utilizand matricea drumurilor
Algoritmul +/-
O componenta tare conexa este un subgraf al sau care este tare conex si care este maximal in raport cu aceasta proprietate.
Observatie: reunind toate arcele din componentele tare conexe se poate obtine o multime mai mica decat multimea arcelor grafului initial.
Se poate construi un graf al componentelor tare conexe in care fiecare componenta tare conexa formeaza un nod iar arcele simuleaza legaturile dintre ele.

Grafuri hamiltoniene
Lant hamiltonian: lant elementar care contine toate nodurile grafului.
Ciclu hamiltonian: ciclu elementar care contine toate nodurile grafului.
Graf hamiltonian: graf care contine un ciclu hamiltonian.


Grafuri euleriene
Ciclu eulerian: ciclu care trece prin toate muchiile unui graf exact o data.
Graf eulerian: graf care contine cel putin un ciclu eulerian.