Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate didacticaScoala trebuie adaptata la copii ... nu copiii la scoala





Biologie Botanica Chimie Didactica Fizica Geografie
Gradinita Literatura Matematica




Matematica


Qdidactic » didactica & scoala » matematica
Concepte de baza in teoria grafurilor: semigraf exterior, interior, nod, drum, circuit



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: (x1, x2, , xk), cu

proprietatea ca exista in graf toate arcele de forma (xi,xi+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 xi Є X in graful G: numarul de noduri la care se poate ajunge din xi. Puterea de atingere se noteaza cu p(xi), 1 i n si evident p(xi) δ+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'(xi) = G(xi) 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).







Contact |- ia legatura cu noi -|
Adauga document |- pune-ti documente online -|
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -|
Copyright © |- 2022 - Toate drepturile rezervate -|