Page 33 - MATINF Nr. 9-10

Caracteriz˘ari pentru secvent , e grafice 33

Pas Gradele r˘amase Muchia ad˘augat˘a
1 1, 1, 1, 1, 2, 2, 3, 13 [v 1 , v 2 ]
2 0, 0, 1, 1, 2, 2, 3, 13 [v 3 , v 4 ]
3 0, 0, 0, 0, 2, 2, 3, 13 [v 5 , v 6 ]
4 0, 0, 0, 0, 1, 1, 3, 13 [v 5 , v 6 ]
5 0, 0, 0, 0, 0, 0, 3, 13 [v 7 , v 8 ]
6 0, 0, 0, 0, 0, 0, 2, 12 [v 7 , v 8 ]
7 0, 0, 0, 0, 0, 0, 1, 11 [v 7 , v 8 ]
8 0, 0, 0, 0, 0, 0, 0, 10 [v 8 , v 8 ] de 5 ori
– 0, 0, 0, 0, 0, 0, 0, 0 –

a
Graful general obt , inut are matricea de adiacent , ˘
 
0 1 0 0 0 0 0 0
 1 0 0 0 0 0 0 0 
 
0 0 0 1 0 0 0 0
 
 
0 0 1 0 0 0 0 0
 
A =   .
0 0 0 0 0 2 0 0
 
 
 0 0 0 0 2 0 0 0 
 
 0 0 0 0 0 0 0 3 
0 0 0 0 0 0 3 5
Evident, acest graf nu este singurul cu gradele date. De exemplu, dac˘ dorim s˘ minimiz˘am
a
a
num˘arul de bucle, atunci ad˘aug˘am de fiecare dat˘a muchie ˆıntre dou˘a noduri de grade nenule
maxime. Pe de alt˘a parte, dac˘a dorim s˘a maximiz˘am num˘arul de bucle, atunci ad˘aug˘am ˆıntˆai
bucle, cˆat timp exist˘a grade mai mari sau egale cu 2.

Caracterizarea gradelor unui multigraf

Propozit , ia 3. Fie d 1 , d 2 , . . . , d n ∈ N astfel ˆıncˆat d 1 ≤ d 2 ≤ . . . ≤ d n , unde n ∈ N, n ≥ 2.
a
Atunci numerele d 1 , d 2 , . . . , d n sunt gradele nodurilor unui multigraf neorientat cu n noduri dac˘
n n−1
P P
s , i numai dac˘ suma d i este un num˘ar par s , i d n ≤ d i .
a
i=1 i=1
n
P
Demonstrat¸ie. ”⇒” Conform Propozit , iei 1 avem d i = 2m, unde m este num˘arul de muchii
i=1
a
ale multigrafului neorientat avˆand gradele nodurilor d 1 , d 2 , . . . , d n , deci suma considerat˘ este un
n−1
P
num˘ar par. De asemenea, avem d n = a i , unde, pentru orice i ∈ {1, . . . , n − 1}, a i reprezint˘
a
i=1
num˘arul de muchii de forma [v n , v i ]. Cum a i ≤ d i pentru orice i ∈ {1, . . . , n − 1}, rezult˘a c˘a
n−1
d n ≤ P d i .
i=1
n n−1
P P
a
a
”⇐” Ar˘at˘am c˘ dac˘ d i = 2m cu m ∈ N, d 1 ≤ d 2 ≤ . . . ≤ d n s , i d n ≤ d i , atunci exist˘a
i=1 i=1
un multigraf neorientat G = (V, E) cu V = {v 1 , . . . , v n } astfel ˆıncˆat d G (v i ) = d i , ∀i ∈ {1, . . . , n}.
Pentru n = 2 rezult˘a c˘a d 1 = d 2 , deci considerˆand multigraful neorientat G = (V, E), cu
V = {v 1 , v 2 } s , i E = {e 1 , . . . , e m }, unde m = d 1 = d 2 s , i e k = [v 1 , v 2 ], ∀ k ∈ {1, . . . , m}, iar