Notiuni introductive

Graf <=> Orice multime finita V, inzestrata cu o relatie binara interna E. Notam graful cu G = (V,E)

Graf neorientat <=> Un graf G = (V,E) in care relatia binara este simetrica: daca (x,y) apartine lui E, atunci (y,x) apartine lui E.

Graf orientat <=> Un graf G = (V,E) in care relatia binara nu este simetrica.

Node <=> Element al multimii V, unde G = (V,E) este un graf neorientat.

Varf <=> Element al multimii V, unde G = (V,E) este un graf orientat sau neorientat.

Muchie <=> element al multimii E ce descrie o relatie existanta intre doua varfuri din V, unde G = (V,E) este un graf neorientat. Muchiile unui graf neorientat sunt considerate ca neavand o directie, deci pot fi parcurse in ambele sensuri.

Arc <=> Element al multimii E ce descrie o relatie existanta intre doua varfuri ale lui V, unde G = (V,E) este graf orientat. Arcele sunt parcurse in directia data de relatia Varf -> VarfSuccesor

Adiacenta <=> Varful x este adiacent cu y daca perechea (x,y) apartine lui E. Intr-un graf neorientat, existenta muchiei (x,y) presupune ca x este adiacent cu y si y este adiacent cu x.

Incidenta <=> o muchie este incidenta cu un nod daca il are pe acesta ca extremitate. Muchia (x,y) este incidenta in nodul x, respectiv in y.

Incidenta spre interior <=> Un arc este incident spre interior cu un varf, daca il arepe acesta ca varf terminal. Arcul converge spre varf. Arcul (x,y) este incident spre interior cu varful y.

Incidenta spre exterior <=> Un arc este incident spre exterior cu un varf daca il are pe acesta ca varf initial(arcul pleaca din varf). Arcul (x,y) este incident spre exterior cu varful x.

Grad <=> Gradul unui nod x, dintr-un graf neorientat, este un numar ce reprezinta numarul de noduri adiacente cu acesta.

Gradul interior <=> In cazul unui graf orientat, fiecare nod x are asociat un numar numit grad interior si care este egal cu numarul de arce care il au pe x ca varf terminal (numarul de arce incidente spre interior).

Gradul exterior <=> In cazul unui graf orientat, fiecare nod are asociat un numar numit grad exterior si care este egal cu numarul de arce care il au pe x ca varf initial(numarul de arce incidente spre exterior).

Varful izolat <=> un varf cu gradul 0.

Varful terminal <=> un varf cu gradul 1.

Lant <=> este o secventa de noduri ale unui graf neorientat G = (V, E) cu proprietatea ca oricare doua noduri consecutive sunt adiacente.

Lungimea unui lant <=> numarul de muchii din care este format.

Lant simplu <=> un lant care contine numai muchii distincte.

Lant compus <=> lantul care nu este format numai din muchii distincte.

Lant elementar <=> lantul care contine numai noduri distincte.

Ciclu <=> un lant in care primul nod coincide cu ultimul. Ciclul este elementar daca este format doar din noduri distincte, exceptie facand primul si ultimul. Lungimea minima a unui ciclu este 3.

Drum <=> Este o secventa de varfuri ale unui graf orientat G = (V,E) cu proprietatea ca oricare doua varfuri consecutive sunt adiacente.

Lungimea unui drum <=> numarul de arce din care este format.

Drum simplu <=> drumul care contine arce distincte.

Drum compus <=> drumul care nu este format din arce distincte.

Drum elementar <=> drum care contine numai varfuri distincte.

Circuit <=> Un drum in care primul varf coincide cu ultimul varf. Circuitul este elementar daca este format doar din varfuri distincte, exceptie facand primul si ultimul.

Graf partial <=> Un Graf G’=(V,E’) reprezinta graf partial al grafului G = (V,E) daca E’ este inclus in E. Cu alte cuvinte G este graf partial al lui G, daca este identic sau se obtine prin suprimarea unor muchii, respectiv arce din G.

Subgraf <=> Un subgraf al lui G este un graf G’=(V’,E’) in care V’ este inclus in V, iar V’ contine toate muchiile/arcele din E ce au ambele extremitati in V’. Cu alte cuvinte G este un subgraf al lui G, daca este identic sau se obtine prin suprimarea unor noduri impreuna cu muchiile sau arcele incidente cu acestea.

Graf regulat <=> un graf neorientat in care toate nodurile au acelasi grad.

Graf complet <=> graf neorientat G = (V,E) intre oricare doua noduri. Numarul de muchii ale unui graf complet este V * V-1 /2.

Graf conex <=> graf neorientat G = (V,E) in care, pentru orice pereche de varfuri (x,y) exista un lant care le uneste.

Graf tare conex <=> graf orientat G = (V,E) in care, pentru orice pereche de varfuri (x,y) exista un drum de la (x,y) si un drum de la (y,x).

Componenta conexa <=> subgraf al grafului de referinta, maximal in raport cu proprietatea de conexitate(intre oricare doua varfuri exista lant).

Lant hamiltonian <=> un lant elementar care contine toate varfurile grafului.

Ciclu hamiltonian <=> un ciclu hamiltonian care contine toate nodurile grafului.

Graf hamiltonian <=> un graf care contine un ciclu hamiltonian.

Daca G este un graf cu n >= 3 varfuri, astfel incat gradul oricarui varf verifica inegalitatea: gr(x) >= n/2, rezulta ca G este graf hamiltonian.

Lant eulerian <=> un lant simplu care contine toate muchiile unui graf.

Ciclu eulerian <=> un ciclu simplu care contine toate muchiile grafului.

Graf eulerian <=> un graf care contine un ciclu eulerian.

Un graf este eulerian daca si numai daca oricare varf al sau are gradul par.