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:
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.