Arbore liber
Un arbore este un graf conex și aciclic. Se mai numește și arbore liber.
Următoarele propoziții sunt adevărate:
- Un arbore cu
n
vârfuri aren-1
muchii. - Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex.
- Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, s-ar obține un ciclu.
- Între oricare două vârfuri ale unui arbore există un lanț elementar unic.
Arbori cu rădăcină
Pentru un arbore se poate stabili un nod special, numit rădăcină. Putem spune că “agățăm” arborele în rădăcină, iar restul nodurilor cad.
Mai jos avem trei arbori cu rădăcină. Toți pornesc de la arborele de mai sus, dar diferă prin alegerea rădăcinii.
Terminologie
Fie un arbore cu rădăcina r
și x
un nod în acest arbore. Atunci:
- se numește ascendent al lui
x
orice nody
, diferit dex
, aflat pe lanțul de la rădăcină lax
;- rădăcina nu are ascendenți;
- rădăcina este ascendent pentru toate nodurile din arbore;
- dacă
y
este ascendent al luix
și există muchia(y,x)
, atunciy
se numește ascendent direct al luix
sau tatăl luix
;- rădăcina este singurul nod din arbore care nu are tată;
- un nod
y
este descendent al noduluix
, diferit dey
, dacăx
aparține lanțului de lar
lay
;- dacă în plus există muchia
(x,y)
, atunciy
este descendent direct sau fiu al luix
; - un nod care nu are niciun descendent se numește frunză;
- dacă în plus există muchia
- două noduri care au același tată se numesc frați;
- lungimea unui lanț de la rădăcina arborelui la un nod
x
reprezintă nivelul sau adâncimea noduluix
; - lungimea maximă a unui lanț de la rădăcină la un nod al arborelui reprezintă înălțimea arborelui;
- un nod al arborelui împreună cu toți descendenții săi formează un subarbore;
Exemplu
Fie arborele următor:
- rădăcina arborelui este nodul
3
; - ascendenții nodului
4
sunt5
,2
și3
. Ascendentul direct (tatăl) al nodului4
este nodul5
; - descendenții nodului
2
sunt1 7 10 5 4 6
. Descendenții direcți ai nodului2
sunt1 5
; - nodurile
1
și5
sunt frați; - nodurile
6 7 8 10 12
sunt frunze; - descompunerea pe niveluri:
- Nivelul
0
conține doar rădăcina:3
; - Nivelul
1
conține nodurile2 9
; - Nivelul
2
conține nodurile1 5 8 11
; - Nivelul
3
conține nodurile7 10 4 12
; - Nivelul
4
conține nodul6
;
- Nivelul
- Înălțimea arborelui este
4
; - Nodurile
9 8 11 12
formează un subarbore;
Reprezentarea arborilor
Reprezentarea prin referințe descendente
Pentru fiecare nod al arborelui se memorează informații despre descendenții săi direcți. Este similară cu reprezentarea prin liste de adiacențe a grafurilor. Pentru arborele de mai sus avem:
F[1]={7,10}
F[2]={1,5}
F[3]={2,9}
F[4]={6}
F[5]={4}
F[6]={}
F[7]={}
F[8]={}
F[9]={8,11}
F[10]={}
F[11]={12}
F[12]={}
Reprezentarea prin referințe ascendente
Pentru fiecare nod se memorează informații despre ascendenții direcți. Vom obține un vector de tați, în care:
t[r] = 0
, under
este rădăcina arboreluit[k] =
tatăl noduluik
Pentru arborele de mai sus avem:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
t[k] |
2 |
3 |
0 |
5 |
2 |
4 |
1 |
9 |
3 |
1 |
9 |
11 |
Observații
- În vectorul de tați există o singură valoare
0
, corespunzătoare rădăcinii; - Frunzele corespund valorilor care nu apar în vectorul de tați.
- Vectorul de tați ne permite să determinăm lanțuri în arbore, de la un nod oarecare spre rădăcină:
- Pornim de la un nod dat
x
- Identificăm tatăl lui
x
,y = t[x]
; - Identificăm tatăl lui
y
,t[y]
- ș.a.m.d.
- Ajungem într-un nod
z
pentru caret[z]=0
. acesta va fi rădăcina și ne oprim.
- Pornim de la un nod dat