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

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.