(ˆVˆ <=> |V| -cardinal de V)

Definitie: t4c11ch
Fie G = (V, E) o multime, Œn care V este o multime de noduri finita, ˆVˆ = n , si E o multime de arce,
E = A(i, j), i, j N S. G se numeste graf, E<=VxV.
Avem: grafuri orientate Œn care (i, j)1=(j, i) grafuri neorientate Œn care (i, j)apartine lui E->(j, i)apartine lui E

Observatie: Un arbore este un caz particular de graf.

Definitii: i se numeste predecesor al lui j; j se numeste succesor al lui i;
(i, j) este adiacent cu i si j; i, j adiacente;
Ei = A k, (k, i) ES multimea de vecini la intrare;
E'i = A j, (i, j) ES multimea de vecini la iesire;
Ei reunit E'i multimea vecinilor. grad_intrare(i) = in_degree(i) = ˆEiˆ grad_ie_ire(i) = out_degree(i) = ˆ E'iˆ
Pentru un graf neorientat (G - neorientat), Ei E'i si degree(i)= ˆEiˆ.

Definitie
Se numeste drum orientat Œntr-un graf de la x la y secventa de noduri
D = (i1 = x, i2, ... , in = y),
(ik, ik+1) E, k=1,n . (ik <=> i indoce k)
Drumul D este neorientat, daca (ik, ik+1) apartine E sau (ik+1, ik)apartine E

Definitie
Se numeste graf conex graful pentru care doua noduri (x, y) V, D un drum de la x la y.
Un graf este complet daca fiecare nod este conectat cu oricare din celelalte noduri: E = VxV \ A(i, i), iaprtine VS

Definitie
Fie G = (V, E) un graf. Se numeste subgraf al grafului G, un graf
G' = (V', E'), astfel Œncƒt V' inclus in V,
E'<=(V'xV') intersectat cu E

Reprezentari
1) Matrice de adiacenta
Fie G = (V, E) ,ˆVˆ = n. Se determina matricea de adiacenta astfel:

Un graf este etichetat daca o functie definita pe E R, adica fiecarui arc i se asociaza o valoare. Astfel de grafuri se reprezinta prin matrici de colectivitate:

Complexitate:
O(1), (i, j) apartine E
O(n), Ei, E'i, indegree(i), outdegree(i)
O(n2), spatiu

1) Liste de adiacenta directa

Definitie
Fie G = (V, E) un graf, ˆVˆ = n , V = A1, 2, ... , nS. Se numeste lista de adiacenta asociata acestui graf o colectie de n pointeri (1, 2, ... , n), fiecare pointer continƒnd adresa unei liste dupa regula urmatoare: L(i) da adresa listei Œnlantuite care contine toti succesorii lui i.

L(i)->Ei

Exemplu:

3) Liste de adiacente inverse
(i,j) apartine E
O(ˆEˆ)- cardinal de E
L'(1, 2, ..., n), L'(i)->E'i
Ei: O(ˆEˆ) sau O(maxout_degree)
E'i: O(ˆEˆ) spatiu: O(ˆEˆ + n)

4) Liste de adiacenta dubla
(i,j) , E, (i,j, e(i,j))

Operatii pe grafuri, traversari
La grafuri se folosesc operatii Œntre elemente ((i,j) adiacente, etc), operatii de traversare pe grafuri. Se numeste traversare pe graf o procedura de traversare, pentru un scop bine definit, prin toate nodurile.
Exista: traversari Œn adƒncime A depth first traversari Œn latime A bmedth first

Proceduri:

dfs(G, i) // mark(1... n) initializat cu
// (00 ... 0) A ext
A // procesare() procesare(i) mark(i) = 1 for fiecare k V cu (i,k) E
| if mark(k) = 0
|_dfs(k)
S

bfs(G, i)
A // mark(1... n) initializat cu (0 ... 0) ext
// o coada q isempty, a= pop(p), put(q) ext procesare(i) mark(i) = 1 put(q, i)
while(isEmpty(q) = N0)) do
| k = pop(q)
| for fiecare j V , (k,j) E
| | if(mark(j)=0)
| | | procesare(j)
| | | mark(j) = 1
| | |_ put(q,j)
S

1) Matrice adiacenta

dfs(M, i)
A procesare(i) mark(i) = 1 for k = 1 to n
| if (M(i,k) = 1)
| | if mark(k) = 0
|_ |_ dfs(k)
S

2) Liste de adiacenta directa

dfs(L, i)
A procesare(i) mark(i) = 1 p = P(i)
while p 0
| if mark(data(p)) 0
| dfs(data(p))
|_ p = link(p)
S

Arbori de acoperire pe grafuri

Fie G(V, E) un graf.
Se numeste arbore de acoperire un arbore T = (V, E') , cu E'<=E

Observatie: Algoritmii dfs, bfs produc arbori de acoperire.