Page 37 - MATINF Nr. 9-10

Caracteriz˘ari pentru secvent , e grafice 37

este un graf neorientat simplu avˆand gradele nodurilor

d G (v i ) = d G 0(v i ) = d i , pentru 1 ≤ i ≤ n − d n − 1,
0(v i ) + 1 = d i − 1 + 1 = d i , pentru n − d n ≤ i ≤ n − 1,
d G (v i ) = d G
d G (v n ) = d n ,

a
deci (d 1 , d 2 , . . . , d n ) este secvent , ˘ grafic˘a.
Observat ,ia 3. Demonstrat , ia teoremei anterioare este constructiv˘a, ea indicˆand un algoritm
recursiv de generare a unui graf neorientat simplu cu gradele nodurilor date.
Exemplul 5. Verific˘am dac˘a secvent , a (1, 1, 1, 2, 4, 5, 5, 5) din exemplul anterior este secvent , ˘a
grafic˘a. Conform teoremei anterioare avem echivalentele:

(1, 1, 1, 2, 4, 5, 5, 5) este secvent , ˘ grafic˘
a
a
a
⇔ 5 ≤ 7 s , i (1, 1, 0, 1, 3, 4, 4) este secvent , ˘ grafic˘
a
⇔ 4 ≤ 6 s , i (1, 0, 0, 0, 2, 3) este secvent , ˘ grafic˘
a
a
a
⇔ 3 ≤ 5 s , i (0, 0, 0, −1, 1) este secvent , ˘ grafic˘.
a
a
a
a
a
a
Cum ultima secvent , ˘ nu este o secvent , ˘ grafic˘ (deoarece gradele nu pot fi negative), rezult˘ c˘
a
a
nici secvent , a init , ial˘ nu este secvent , ˘ grafic˘a.
a
Exemplul 6. Verific˘am dac˘ secvent , a (1, 1, 2, 3, 4, 5, 5, 5) este secvent , ˘ grafic˘a. Conform teoremei
a
anterioare avem echivalentele:
a
S 1 = (1, 1, 2, 3, 4, 5, 5, 5) este secvent , ˘ grafic˘
a
a
a
⇔ 5 ≤ 7 s , i S 2 = (1, 1, 1, 2, 3, 4, 4) este secvent , ˘ grafic˘
a
a
⇔ 4 ≤ 6 s , i S 3 = (1, 1, 0, 1, 2, 3) este secvent , ˘ grafic˘
a
a
⇔ 3 ≤ 5 s , i S 4 = (1, 0, 0, 0, 1) este secvent , ˘ grafic˘
a
a
⇔ 1 ≤ 4 s , i S 5 = (0, 0, 0, 0) este secvent , ˘ grafic˘.
Cum ultima secvent , ˘a, S 5 , este o secvent , ˘a grafic˘a, fiind secvent , a gradelor grafului simplu cu 4
a
noduri s , i 0 muchii, rezult˘a c˘a s , i secvent , a init , ial˘a, S 1 , este secvent , ˘ grafic˘a.
Mai mult, conform demonstrat , iei teoremei amintite (partea ”⇐”), avem succesiv:
S 5 = (0, 0, 0, 0) este secvent , a gradelor grafului G 5 = ({v 1 , . . . , v 4 }, E 5 ) cu
E 5 = Ø;
S 4 = (1, 0, 0, 0, 1) este secvent , a gradelor grafului G 4 = ({v 1 , . . . , v 5 }, E 4 ) cu
E 4 = E 5 ∪ {[v 5 , v 1 ]};
S 3 = (1, 1, 0, 1, 2, 3) este secvent , a gradelor grafului G 3 = ({v 1 , . . . , v 6 }, E 3 ) cu
E 3 = E 4 ∪ {[v 6 , v 2 ], [v 6 , v 4 ], [v 6 , v 5 ]};

S 2 = (1, 1, 1, 2, 3, 4, 4) este secvent , a gradelor grafului G 2 = ({v 1 , . . . , v 7 }, E 2 ) cu
E 2 = E 3 ∪ {[v 7 , v 3 ], [v 7 , v 4 ], [v 7 , v 5 ], [v 7 , v 6 ]};
S 1 = (1, 1, 2, 3, 4, 5, 5, 5) este secvent , a gradelor grafului G 1 = ({v 1 , . . . , v 8 }, E 1 ) cu
E 1 = E 2 ∪ {[v 8 , v 3 ], [v 8 , v 4 ], [v 8 , v 5 ], [v 8 , v 6 ], [v 8 , v 7 ]}.

Graful G 1 este reprezentat ˆın figura urm˘atoare.