Grafuri. Traversari pe grafuri

Grafuri. Traversari pe grafuri

Definitie:

Fie G = (V, E) o multime, in care V este o multime de noduri finita, │V│ = n , si E o multime de arce,
E = . G se numeste graf, E V V

Avem: grafuri orientate in care (i, j) (j, i)

grafuri neorientate in care (i, j) I E (j, i) 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;

E_i multimea de vecini la intrare;

E'_i multimea de vecini la iesire;

E_i E'_i multimea vecinilor.

grad_intrare(i) = in_degree(i) = │E_i

grad_ie_ire(i) = out_degree(i) = │ E'_i

Pentru un graf neorientat (G - neorientat), E_i s E'_i si degree(i)= │E_i

Definitie

Se numeste drum orientat intr-un graf de la x la y secventa de noduri D = (i = x, i i_n = y)

(i_k, i_k+1 I E .

Drumul D este neorientat, daca (i_k, i_k+1 I E sau (i_k+1, i_k I E

Definitie

Se numeste graf conex graful pentru care doua noduri (x, y) I 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

Definitie

Fie G = (V, E) un graf. Se numeste subgraf    al grafului G, un graf G' = (V', E'), astfel incat V' V,
E' (V' V') 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) I E

O(n), E_i, E'_i, indegree(i), outdegree(i)

O(n ), spatiu

1) Liste de adiacenta directa

Definitie

Fie G = (V, E) un graf, │V│ = n , V = . Se numeste lista de adiacenta asociata acestui graf o colectie de n pointeri < n), fiecare pointer continand adresa unei liste dupa regula urmatoare: L(i) da adresa listei inlantuite care contine toti succesorii lui i.

L(i) E_i

Exemplu:

3) Liste de adiacente inverse

(i,j) I E

O(│E│) cardinal de E

L'(1, 2, , n), L'(i) E'_i

E_i: 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 intre 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 in adancime — depth first

traversari in latime — bmedth first

Proceduri:

dfs(G, i) // mark(1 n) initializat cu

// (00 0) — ext

bfs(G, i)

1) Matrice adiacenta

dfs(M, i)

2) Liste de adiacenta directa

dfs(L, i)

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.