Page 32 - MATINF Nr. 9-10

32 C. B˘alc˘au

∗
Propozit , ia 2. Fie d 1 , d 2 , . . . , d n ∈ N, unde n ∈ N . Atunci numerele d 1 , d 2 , . . . , d n sunt gradele
n
P
a
nodurilor unui graf neorientat general cu n noduri dac˘ s , i numai dac˘ suma d i este un num˘ar
a
i=1
par.
n
P
Demonstrat¸ie. ”⇒” Conform Propozit , iei 1 avem d i = 2m, unde m este num˘arul de muchii
i=1
ale grafului general avˆand gradele nodurilor d 1 , d 2 , . . . , d n , deci suma considerat˘ este un num˘ar
a
par.
n
P
”⇐” Demonstr˘am c˘a dac˘a d i = 2m cu m ∈ N, atunci exist˘a un graf neorientat general
i=1
G = (V, E) cu V = {v 1 , . . . , v n } astfel ˆıncˆat d G (v i ) = d i , ∀ i ∈ {1, . . . , n}, prin induct , ie dup˘ m.
a
Pentru m = 0 rezult˘a c˘a d i = 0, ∀ i ∈ {1, . . . , n}, deci luˆand E = Ø avem d G (v i ) = 0 = d i ,
∀ i ∈ {1, . . . , n}.
∗
Presupunem afirmat , ia adev˘arat˘a pentru m − 1 s , i o demonstr˘am pentru m, unde m ∈ N .
n
P
Fie d i = 2m. Avem dou˘a cazuri.
i=1
a
Cazul 1) Exist˘ j, k ∈ {1, . . . , n}, j 6= k, astfel ˆıncˆat d j ≥ 1 s , i d k ≥ 1. Fie
ß d i − 1, dac˘ i ∈ {j, k},
a
0
d =
i d i , dac˘ i ∈ {1, . . . , n} \ {j, k}.
a
n n
P 0 P
Atunci d = d i − 2 = 2(m − 1), deci, conform ipotezei de induct , ie, exist˘ un graf general
a
i
i=1 i=1
0 0 0
neorientat G = (V, E ) cu V = {v 1 , . . . , v n } astfel ˆıncˆat d G 0(v i ) = d , ∀ i ∈ {1, . . . , n}. Fie graful
i
0 0
general G = (V, E ∪ {e}), unde e = [v j , v k ], e 6∈ E . Evident, avem d G (v j ) = d G 0(v j ) + 1 =
0 0 0
d + 1 = d j , d G (v k ) = d G 0(v k ) + 1 = d + 1 = d k s , i d G (v i ) = d G 0(v i ) = d = d i pentru orice
i
j
k
i ∈ {1, . . . , n} \ {j, k}. Astfel d G (v i ) = d i , ∀ i ∈ {1, . . . , n}.
Cazul 2) Exist˘a j ∈ {1, . . . , n} astfel ˆıncˆat d i = 0 pentru orice i ∈ {1, . . . , n} \ {j}. Atunci
n
P
d j = d i = 2m. Fie graful general G = (V, E), cu V = {v 1 , . . . , v n } s , i E = {e 1 , . . . , e m }, unde
i=1
e k = [v j , v j ], ∀ k ∈ {1, . . . , m}, iar buclele e 1 , . . . , e m sunt distincte dou˘a cˆate dou˘a. Evident,
avem d G (v j ) = 2m = d j s , i d G (v i ) = 0 = d i pentru orice i ∈ {1, . . . , n} \ {j}. Astfel, din nou,
d G (v i ) = d i , ∀ i ∈ {1, . . . , n}.
Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
Observat ,ia 1. Demonstrat , ia propozit , iei anterioare este constructiv˘a, ea indicˆand un algoritm de
generare a unui graf neorientat general cu gradele nodurilor date.
Exemplul 1. Numerele 1, 1, 1, 2, 4, 4, 5, 5 nu pot fi gradele nodurilor unui graf neorientat general,
8
P
deoarece suma d i = 23 este un num˘ar impar.
i=1
Exemplul 2. Numerele 1, 1, 1, 1, 2, 2, 3, 13 pot fi gradele nodurilor unui graf neorientat general,
8
P
deoarece suma d i = 24 este un num˘ar par. Mai mult, conform demonstrat , iei propozit , iei
i=1
anterioare (partea ”⇐”), un graf general avˆand gradele nodurilor numerele date se construies , te
a
ad˘augˆand succesiv cˆate o muchie ˆıntre dou˘ noduri de grade nenule, grade care se mics , oreaz˘ cu
a
0
1, pˆan˘a cˆand fie toate gradele devin egale cu zero, fie r˘amˆane un grad nenul d , par, care este
i
0
anulat s , i el prin d /2 bucle. Acest procedeu este evident , iat ˆın tabelul urm˘ator:
i