Curs Arbori

O prima definitie a structurii de arbore o putem da pornind de la o structura mai complexa, cea de graf. Definitie. Se numeste graf G = (X, V) o pereche formata din doua multimi, multimea X a nodurilor sau virfurilor grafului, si multimea V a muchiilor grafului, unde o muchie v ? V este o pereche ordonata de noduri v=(x,y), x,y ? X.
Un graf neorientat este un graf in care perechea (x,y) se identifica cu perechea (y,x). Un graf fara cicluri este un graf in care, pornind de la un virf dat nu putem ajunge din nou la el folosind muchii.

Definitie. Se numeste arbore un graf H = (X, V) care este neorientat, fara cicluri, cu un nod precizat  numit radacina. Pentru orice varf x? X , exista un numar finit de varfuri x1,...,xn ? X asociate lui x, numite descendenti directi (sau fiii) lui x.