Notiuni introductive:
Fie o multime finita x={x1,x2,…,xn}.Fie G XxX, unde XxX este produsul cartezian al multimii X cu ea însasi.
Definitie. Se numeste graf orientat perechea ordonata G=(x, G).
Elementele xi ? x se numesc noduri sau vârfuri.
Elementele multimii G se numesc arce.Un arc (xk,xi)?G se noteaza si cu [xk,xi].Prin abuz de notatie, vom scrie: [xk,xi]?G.
În concluzie, graful este: G=(x, G)= ({x1,x2,x3,x4},{[x1,x2],[x2,x1],[x3,x4],[x3,x2],[x3,x3]}).
Un graf orientat poate fi reprezentat printr-un desen, asa cum rezulta din imaginea alaturata.
Daca în graful G=(x, G) [x,y]?G vom spune ca x si y sunt adiacente, iar vârfurile x si y sunt incidente cu muchia [x,y].
Daca G=Ø (multimea vida),graful G=(x, G) se numeste graf nul si reprezentarea lui în plan se reduce la puncte izolate.
Definitie.Un graf partial al unui graf orientat dat G=(x, G) este un graf G1=(x, G1) unde G1 Gun graf partial se obtine dintr-un graf suprimand anumite arcuri.
G=(x, G) G1=(x, G1)
Definitie: Un subgraf al unui graf orientat G=(x, G) este un graf H=(x, G1), unde ,iar muchiile din sunt toate muchiile din care au ambele extremitati în multimea Y.
Metode de reprezentare în memorie a unui graf orientat :
Un graf orientat cu n noduri poate fi memorat prin utilizarea unei matrice booleene cu n linii si n coloane, numita matricea de adiacenta:
Ai,j = 1,pentru [i,j] ? G
0,pentru [i,j] ? G
Exemplu: graful orientat urmator se reprezinta astfel:
0 1 0 1
A= 1 0 0 0
0 1 1 1
0 0 0 0
Dezavantajul memorarii unui graf prin matricea de adiacenta este dat de faptul ca multe elemente ale matricei sunt nule, deci se consuma memorie inutil.
Aceasta tehnica se foloseste in rezolvarea problemeor care indeplinesc simultan urmatoarele conditii:
• solutia lor poate fi pusa sub forma u
