Grafuri Teorie

Grafuri Teorie.txt

Un graf este reprezentare abstracta a conectivitatii folosind Nodes si Edges;


- 1...N
- Nodurile si Muchiile sau arcele au informatii
- grafurile : orientate si neorientate
- edges conecteaza m perechi de noduri


Graf = orice multime finita V (Vertices), prevazuta cu o relatie binara interna E

G = (V, E);

Relatie binara = submultime a produsului cartezian VxV


V = {1,2,3,4}
{1,2,3,4} x {1,2,3,4} = 

produsul cartezian = {(1,1),(1,2),(1,3),(1,4), ...}

E = {(1,1),(1,2),(1,3),(1,4)}

relatia binara = simetrica sau non-simetrica

Graf neorientat <=>  un graf G = (V,E) in care relatia vinara este simetrica 

daca (x,y) apartine lui E atunci (y,x) apartine lui E

Graf orientat <=> un graf G = (V,E) in care relatina binara nu este simetrica


Nod <=> orice element al multimii V unde G = (V, E) un graf orientat

Varf

Muchie versus Arc

Adiacenta <=> varful x este adiacent cu varful y daca perechea (x,y) apartine lui E

Incidenta <=> o muchie este incidenta cu un nod daca il are pe acesta la extremitate 

Muchia (x,y) este incidenta cu nodul x respectiv y

Graf <=> gradul unui nod V, dintr-un graf neorientat , este un numar natural ce reprezinta numarul de noduri adiacente cu acesta

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

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

Varf izolat = un varf cu gradul 0

Varf terminal = un varf cu gradul 1

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

w1, w2, w3, ..., wp cu proprietatea (wi, wi+1) apartine lui E cu 1<=i<=p

Ciclu <=> un lant in care primul si ultimul nod coincid, Ciclul este elementar daca este format doar din noduri distincte.

Euler = problema podurilor


Drum = 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 distincte

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

Graf partial <=> Un graf G' = (V', E') reprezinta un graf partial al grafului G = (V,E) daca 
E' inclus in E . Cu alte cuvinte G' este un 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 = (V, E) 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 subgraf al lui G daca este identic sau se obtine prin suprimarea unor noduri impreuna cu muchiile/arcele incidente cu acestea.


Lant hamiltonian = lant elementar care contine toate nodurile unui graf

Ciclu hamiltonian <=> un ciclu elementr care contine toate nodurile grafurlui

Graf hamiltonian <=>  un Graf G care contine un ciclu hamiltonian

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

Graf eulerian = un graf care contine cel putin un ciclul eulerian

Conditiile necesare si suficiente:

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