Arbori - Definire și reprezentare grafică

Un arbore cu $n$ noduri are întotdeauna $n-1$ muchii.

În general, pentru un arbore $G$ cu $n$ muchii, sunt echivalente afirmațiile:

• $G$ este conex minimal (graful nu mai este conex după eliminarea oricărei muchii);
• $G$ este aciclic maximal (orice muchie adăugată va crea un ciclu);
• $G$ este conex $n-1$ muchii;
• $G$ este aciclic cu $n-1$ muchii.

Un graf neorientat care îndeplinește oricare dintre afirmațiile anterioare este arbore.

Un arbore simplu (fără rădăcină) se reprezintă ca un graf neorientat.

Arbore cu rădăcină

Un arbore poate fi reprezentat ca arbore cu rădăcină. Rădăcina corespunde nivelului $0$, continuând ierarhic pentru celelalte noduri.

Graful din exemplul anterior, cu rădăcina în nodul $2$:

Înălțimea arborelui este $2$ (lungimea celui mai lung lanț elementar care pornește din rădăcină).

Arborii cu rădăcină vin cu câțiva termeni specifici pentru noduri, în funcție de poziționarea acestora în graf.

Nod terminal

Nodurile terminale sunt noduri din arbore cu gradul 1.

La noduri terminale se încadrează atât rădăcina (dacă e cazul), cât și extremitățile de pe artere.

Frunză

Frunzele sunt nodurile terminale, cu excepția rădăcinii.

Frunzele pot fi văzute ca și „capetele” arborelui, aflate la extremitățile ramurilor.

Descendent

Orice nod de pe nivelurile următoare unui nod de referință este descendent.

Formăm un subarbore cu rădăcina într-un nod. Toate nodurile mai jos de acesta îi sunt descendenți.

Fiu (descendent direct)

Orice nod de pe un nivel imediat următor este fiu.

Fiii unui nod sunt descendenții legați direct printr-o singură muchie de nodul respectiv.

Ascendent

Orice nod de pe nivelurile anterioare nodului de referință, de pe aceeași ramură, este ascendent.

Nodurile aflate mai sus de un nod ales se numesc ascendenți.

Părinte (tată / ascendent direct)

Nodul de pe nivelul anterior, legat direct de nodul referință, se numește ascendent direct.

Orice nod (în afară de rădăcină) are un singur părinte (ascendent direct).

Frate

Orice nod cu același ascendent direct (același părinte) este nod frate.

Frații se află pe același nivel și au același nod tată.

Aplicarea terminologiei

Revenind la exemplul anterior:

Folosind terminologia definită, să analizăm nodul cu eticheta $3$:

• are $3$ descendenți și toți sunt descendenți direcți;
• este tată pentru $3$ frunze;
• are $4$ frați, dintre care $3$ sunt și frunze în arbore;
• are un singur ascendent, un nod terminal (chiar rădăcina arborelui).

Pentru a obține cel mai înalt arbore vom căuta cel mai lung lanț elementar și vom alege una din extremitățile lanțului drept rădăcină.

Dacă ne dorim cel mai „scund” arbore, procedeul este asemănător. Cu același cel mai lung lanț elementar, alegem rădăcina să fie un nod din mijlocul lanțului.