![](images/title/arbori.jpg)
![](images/def.gif)
Numim arbore un graf neorientat conex si fara
cicluri.
PROPRIETATI ALE ARBORILOR
Teorema 1
Fie G = (V,U) un graf neorientat. Urmatoarele afirmatii
sunt echivalente:
G este arbore
Oricare doua varfuri din G sunt unite printr-un lant simplu unic
G este conex minimal (daca suprimam o muchie, graful obtinut este
neconex)
G este conex si are |V|-1 muchii
G este aciclic si are |V|-1 muchii
G este aciclic maximal (daca adaugam o muchie, graful obtinut
contine cicluri)
Teorema 2
Numerele intregi 0 < d1 <= d2 <= ... <=
dn (n>=2) sunt gradele varfurilor unui arbore daca si numai
daca d1+d2+...+dn = 2*n-2.
ARBORI CU RADACINA
![](images/def.gif)
Un arbore cu radacina este o multime finita
de noduri care fie este vida fie:
- exista un nod special numit radacina arborelui
- multimea celorlalte noduri este partitionata in n>=0 clase
A1, A2, ..., An, fiecare clasa fiind un arbore cu radacina. Radacina
arborelui este unita prin muchii de radacinile arborilor A1, A2,
..., An.
|