Arbori

fie g un graf orientat. g este un arbore cu radacina r, daca exista in g un varf r din care oricare alt varf poate fi ajuns printr-un drum unic.
definitia este valabila si pentru cazul unui graf neorientat, alegerea unei radacini fiind insa in acest caz arbitrara orice arbore este un arbore cu radacina, iar radacina poate fi fixata in oricare varf al sau. aceasta, deoarece dintr-un varf oarecare se poate ajunge in oricare alt varf printr-un drum unic.
cand nu va fi pericol de confuzie, vom folosi termenul arbore, in loc de termenul corect arbore cu radacina. cel mai intuitiv este sa reprezentam un arbore cu radacina, ca pe un arbore propriu-zis. in figura 3.1, vom spune ca beta este tatal lui delta si fiul lui alpha, ca beta si gamma sunt frati, ca delta este un descendent al lui alpha, iar alpha este un ascendent al lui delta. un varf terminal este un varf fara descendenti. varfurile care nu sunt terminale sunt neterminale. de multe ori, vom considera c...