Page 35 - MATINF Nr. 9-10

Caracteriz˘ari pentru secvent , e grafice 35

Observat ,ia 2. Demonstrat , ia propozit , iei anterioare este constructiv˘a, ea indicˆand un algoritm de
generare a unui multigraf neorientat cu gradele nodurilor date.
Exemplul 3. Numerele 1, 1, 1, 1, 2, 2, 3, 13 din exemplul anterior nu pot fi gradele nodurilor unui
8 7
P P
multigraf neorientat, deoarece suma d i = 24 este un num˘ar par, dar d 8 = 13 > 11 = d i .
i=1 i=1
Exemplul 4. Numerele 1, 1, 1, 2, 4, 5, 5, 5 pot fi gradele nodurilor unui multigraf neorientat,
8 7
P P
deoarece suma d i = 24 este un num˘ar par s , i d 8 = 5 ≤ 19 = d i . Mai mult, conform
i=1 i=1
demonstrat , iei propozit , iei anterioare (partea ”⇐”), un multigraf avˆand gradele nodurilor numerele
a
date se construies , te ad˘augˆand succesiv cˆate o muchie ˆıntre dou˘ noduri de grade nenule maxime,
grade care se mics , oreaz˘ cu 1, pˆan˘ cˆand gradele devin toate egale cu zero. Acest procedeu este
a
a
evident , iat ˆın tabelul urm˘ator:
Pas Gradele r˘amase Muchia ad˘augat˘a
1 1, 1, 1, 2, 4, 5, 5, 5 [v 7 , v 8 ]
2 1, 1, 1, 2, 4, 5, 4, 4 [v 6 , v 8 ]
3 1, 1, 1, 2, 4, 4, 4, 3 [v 6 , v 7 ]
4 1, 1, 1, 2, 4, 3, 3, 3 [v 5 , v 8 ]
5 1, 1, 1, 2, 3, 3, 3, 2 [v 6 , v 7 ]
6 1, 1, 1, 2, 3, 2, 2, 2 [v 5 , v 8 ]
7 1, 1, 1, 2, 2, 2, 2, 1 [v 6 , v 7 ]
8 1, 1, 1, 2, 2, 1, 1, 1 [v 4 , v 5 ]
9 1, 1, 1, 1, 1, 1, 1, 1 [v 7 , v 8 ]
10 1, 1, 1, 1, 1, 1, 0, 0 [v 5 , v 6 ]
11 1, 1, 1, 1, 0, 0, 0, 0 [v 3 , v 4 ]
12 1, 1, 0, 0, 0, 0, 0, 0 [v 1 , v 2 ]
– 0, 0, 0, 0, 0, 0, 0, 0 –

a
Multigraful 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 1 0 0 0
 
A =   .
 0 0 0 1 0 1 0 2 
 
 0 0 0 0 1 0 3 1 
 
 0 0 0 0 0 3 0 2 
0 0 0 0 2 1 2 0
Caracterizarea gradelor unui graf simplu

∗
Definit , ia 1. O secvent ,˘a (d 1 , d 2 , . . . , d n ) de numere naturale (n ∈ N ) se numes , te secvent , ˘a
a
a
grafic˘a (secvent , ˘a de grade, s , ir grafic, s , ir de grade) dac˘ exist˘ un graf neorientat simplu
G = (V, E) cu V = {v 1 , v 2 , . . . , v n } astfel ˆıncˆat d G (v i ) = d i , ∀ i ∈ {1, 2, . . . , n}.
Teorema 1 (Havel-Hakimi). Fie d 1 , d 2 , . . . , d n ∈ N astfel ˆıncˆat d 1 ≤ d 2 ≤ . . . ≤ d n s , i d n ≥ 1,
a
a
a
unde n ∈ N, n ≥ 2. Atunci (d 1 , d 2 , . . . , d n ) este o secvent ,˘ grafic˘ dac˘ s , i numai dac˘ d n ≤ n−1
a
a
− 1, d n−d n+1 − 1, . . . , d n−1 − 1) este secvent ,˘ grafic˘a.
s , i (d 1 , d 2 , . . . , d n−d n−1 , d n−d n