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.

grafuri

Numim graf o pereche ordonată de mulţimi, notată G=(X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numeşte orientat, altfel acesta este neorientat.Aşadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) şi din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).
Grafuri neorientate
Se numeste graf neorientat, o pereche ordonata de multimi notata G=(X,U), unde X={x1,x2,...,xn} este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U={u1,u2,...,un} este o multime de perechi neordonate de elemente din X numite muchii. Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte(noduri,varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii,arce). Exemplu: G=(X,U) X={1,2,3,4,5,6,7,8,9,10} U={(1,2);(1,3);(1,5);(2,3);(6,7);(6,10);(7,8);(8,9);(9,10)}
Nod = element al mulţimii V, unde G=(V, E) este un graf neorientat. Muchie = element al mulţimii E ce descrie o relaţie existentă între două vârfuri din V, unde G=(V, E) este un graf neorientat;
Adiacenta: Într-un graf neorientat existenţa muchiei (v,w) presupune că w este adiacent cu v şi v adiacent cu w. Incidenţă = o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w. Grad = Gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv) Nod izolat = Un nod cu gradul 0. Nod terminal= un nod cu gradul 1
Graf complet = graf neorientat G=(V,E) în care există muchie între oricare două noduri.
Numărul de muchii ale unui graf complet este: nr*(nr-1)/2.Unde nr este numarul de noduri
graf complet. Nr de muchii: 4x(4-1)/2 = 6
Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulţimii X(G), şi notăm această valoare cu G .