Page 31 - MATINF Nr. 9-10

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Caracteriz˘ari pentru secvente grafice
,

Costel B˘alc˘au 1

Grafurile sunt modele matematice cu o gam˘a larg˘a de aplicat , ii. Aceast˘a aplicabilitate a
condus la dezvoltarea accelerat˘a a teoriei grafurilor, atˆat din punct de vedere al rezultatelor
teoretice cˆat s , i al algoritmicii, grafurile impunˆandu-se drept modele fundamentale ˆın informatic˘a.
ˆ a
In acest articol vom prezenta condit , ii necesare s , i suficiente ca o secvent , ˘ de numere naturale
a
s˘ fie s , irul gradelor unui graf neorientat.

Introducere

ˆ
Intr-un graf neorientat G = (V, E), gradul unui nod x, notat cu d(x) = d G (x), reprezint˘a
num˘arul de muchii incidente cu acel nod.
a
Ment , ion˘am c˘ terminologia specific˘ teoriei grafurilor nu este unificat˘ s , i astfel recomand˘am
a
a
ca la parcurgerea unui material despre grafuri s˘ fim atent , i la definirea conceptelor utilizate.
a
ˆ
In articolul de fat , ˘a, ˆıntr-un graf (numit s , i graf simplu) neorientat G = (V, E) muchiile sunt
perechi neorientate [x, y] de noduri distincte s , i orice dou˘ muchii sunt diferite.
a
Pe de o parte, dac˘a permitem existent , a de muchii de forma [x, x], numite bucle, spunem
ˆ
c˘a avem de-a face cu un pseudograf. In acest caz, orice bucl˘a [x, x] se num˘ar˘a de dou˘a ori la
a
calculul gradului nodului x. Pe de alt˘ parte, dac˘ permitem existent , a de muchii multiple (adic˘
a
a
muchii care au aceleas , i extremit˘t , i s , i astfel dou˘ noduri pot fi conectate prin mai multe muchii),
a
a
dar doar ˆıntre noduri distincte, spunem c˘a avem de-a face cu un multigraf. Mai general, dac˘a
permitem existent , a de orice muchii multiple, inclusiv bucle multiple, spunem c˘ avem de-a face
a
cu un graf general.
Caracterizarea gradelor unui graf general

Propozit , ia 1 (Euler). Fie G = (V, E) un graf neorientat general avˆand m muchii. Atunci
P
d(x) = 2m.
x∈V

Demonstrat¸ie. Fiecare muchie e = [v i , v j ] ∈ E (din cele m muchii) contribuie cu 1 la d(v i ) s , i cu
P
1 la d(v j ) (cu 2 la d(v i ) dac˘a v i = v j , adic˘a e = bucl˘a), deci cu 2 la suma d(x). Rezult˘a c˘a
x∈V
a
aceast˘ sum˘ este egal˘ cu 2m.
a
a
1
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com
31