Grafuri

Aplicaţia1: Definiţi matematic tipurile de graf, după tipul de legături dintre vârfurile lor.

Răspuns:

Se cer definiţiile grafului orientat, şi respectiv neorientat.

Rezolvare:

[graful orientat] se notează cu G (X, ), unde: ↑ ↑ cuplul de 2 componente: X şi

∙X (mulţime) nevidă + finită de n elemente, numite vârfuri ale lui G (sau noduri ale lui G, sau puncte ale lui G) şi notate cu [x1, x2, ,xn] (sau prescurtat: [1, 2, , n]), iar: în sensul că are importanţă (contează) ordinea elementelor în pereche

∙ (o mulţime de perechi ordonate de 2 elemente din X, numite arce ale lui G (sau conexiuni directe ale lui G, sau linii ale lui G) şi notate prin (xi, xj) (sau prescurtat: (i, j)), i, j = , cu i j. între paranteze rotunde, între paranteze rotunde,

de pereche ordonată, de pereche ordonată,

cele 2 elemente xi, xj cele 2 elemente i, j

ale lui X ale lui X

(perechea ordonată, (perechea ordonată,

de elemente: xi, xj, ale lui X, de elemente: i, j, ale lui X,

sau perechea ordonată, sau perechea ordonată,

formată din elementele: formată din elementele:

xi, xj ale lui X) i, j ale lui X)

Observaţia1: Cazul i = j în cadrul perechii ordonate (i, j) conduce la perechea ordonată (i, i), numită buclă. Se vor considera numai grafuri orientate fără bucle.

Observaţia2: Pentru arcul (i, j) al lui G (pe scurt pentru (i, j) ), vârfurile i şi j ale lui G s.n. extremităţile arcului; mai precis:

-vârful „i” al lui G s.n. nod iniţial al lui (i, j) (sau extremitate iniţială a lui (i, j)), iar:

-vârful „j” al lui G s.n. nod final al lui (i, j) (sau extremitate finală a lui (i, j)).

Remarcă:

nod nod

iniţial final

al lui (i, j) al lui (i, j) (i, j) ← arc incident cu vf - le i şi j ale lui G (adică arc, ale cărui extremităţi sunt vârfurile i şi j ale lui G)↑ ↑

extremitate extremitate

iniţială finală

a lui (i, j) a lui (i, j)

Vârfurile „i” şi „j” de mai sus s. n. vârfuri adiacente, pentru că un arc ce le uneşte.

[graful neorientat finit] notat cu G (X, ), unde: ↑ ↑ cuplul de 2 componente X şi

∙X (mulţime) nevidă + finită de n elemente, numite vârfuri ale lui G (sau noduri ale lui G, sau puncte ale lui G) şi notate cu: x1, x2, ,xn (sau prescurtat, sau pe scurt: 1, 2, , n), iar: în sensul că nu are importanţă (nu contează) ordinea elementelor în pereche

∙ (o mulţime de perechi neordonate de 2 elemente din X, numite muchii ale lui G şi notate prin [xi, xj] (sau prescurtat, pe scurt : [i, j]), i,

j = , cu i j. între () - ze drepte între paranteze drepte cele 2 elemente cele 2 elemente ale lui X i, j ale lui X. xi şi xj.

Remarcă: Pentru muchia [i, j], vârfurile i şi j ale lui G s.n. extremităţile acestei muchii. În cazul grafurilor neorientate finite, nu se mai face distincţie între extremitatea iniţială şi cea finală a muchiilor lor, întrucât [i, j] este identică cu (coincide cu) [j, i].

Aplicaţia2: Prelucrarea unui produs se realizează prin efectuarea a 6 operaţii, care trebuie să respecte următoarele restricţii:

-P1 trebuie să fie ultima operaţie;

-după P2 pot urma P1, P3 sau P6;

-după P3 poate urma doar P1;

-după P4 pot urma P3, P5 sau P6;

-după P5 pot urma P1, P2 sau P6;