Concepte de baza in teoria grafurilor: semigraf exterior, interior, nod, drum, circuit

Concepte de baza in teoria grafurilor

1. semigraf interior al unui nod xk: este multimea arcelor U^-_xk= care sunt incidente spre interior nodului xk;

2. semigraf exterior al unui nod xk: este multimea arcelor U⁺_xk= care sunt incidente spre exterior nodului xk;

3. semigradul interior al unui nod xk: este numarul arcelor care sunt incidente spre interior nodului xk = cardinalul lui U^-_xk si se noteaza cu δ^-_xk;

4. semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente spre exterior nodului xk = cardinalul lui U⁺_xk si se noteaza cu δ⁺_xk;

5. gradul unui nod xk: este suma semigradelor nodului xk: δ_xk = δ⁺_xk + δ^-_xk;

6. nod izolat: este un nod cu gradul 0;

7. nod suspendat: este un nod cu gradul 1;

8. arce adiacente: arce care au o extremitate comuna;

9. drum intr-un graf: o multime ordonata de noduri ale grafului: (x₁, x₂, , x_k), cu

proprietatea ca exista in graf toate arcele de forma (x_i,x_i+1) i = 1,,k-1;

10. lungimea unui drum: este numarul arcelor care il formeaza;

11. drum elementar: un drum in care fiecare nod apare o singura data;

12. drum simplu: un drum in care fiecare arc apare o singura data;

13. putere de atingere a unui nod x_i Є X in graful G: numarul de noduri la care se poate ajunge din x_i. Puterea de atingere se noteaza cu p(x_i), 1 i n si evident p(x_i) δ⁺_xk

14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;

15. drum eulerian: un drum simplu care contine toate arcele grafului;

16. lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;

17. circuit: un drum in care nodul initial coincide cu cel final;

18. circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

19. circuit simplu: un drum in care fiecare arc apare o singura data;

20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

21. ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;

22. ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

23. ciclu simplu: un ciclu in care fiecare arc apare o singura data;

Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de

asemenea cele de circuit si ciclu.

24. graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' inclus U;

25. subgraf al unui graf G = (X,G): este un graf G'(X',G') unde X' inclus X si G'(x_i) = G(x_i) n X' pentru orice xi X';

26. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este formata din multimile unei partitii de multimi nevide ale lui X, iar ( ) exista doar daca i j si

exista cel putin un arc in U, de la un nod din X^*_i la un nod din X^*_j;

27. graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;

28. graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant;

Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt

echivalente, graful numindu-se doar conex;

29. componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).