Grafuri

GRAFURI. TRAVERSARI PE GRAFURI

Definitie:

Fie G = (V, E) o multime, în care V ¾ este o multime de noduri finita, ¦V¦ = n , si E ¾ o multime de arce, E = {(i, j), i, j Î N }. G se numeste graf, E £ V´V.

Avem: grafuri orientate în care (i, j) ¹ (j, i)

grafuri neorientate în care (i, j) Î E ® (j, i) Î 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 = { k, (k, i) Î E} ¾ multimea de vecini la intrare;

- E'i = { j, (i, j) Î E} ¾ multimea de vecini la iesire;

- Ei È 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, .

Drumul D este neorientat, daca (ik, ik+1) Î E sau (ik+1, ik) Î 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 = V´V {(i, i), i Î V}

Definitie

Fie G = (V, E) un graf. Se numeste subgraf al grafului G, un graf G' = (V', E'), astfel încât V'Ì V, E' £ (V'´V') Ç E

Reprezentari

1) Matrice de adiacenta

Fie G = (V, E) ,¦V¦ = n. Se determina matricea de adiacenta

astfel: