Un arbore este un model abstract al unei relaţii ierarhice El este un caz particular de graf neorientat şi din constă din noduri aflate în relaţii de tip fiu-părinte.

Un arbore cu rădăcină este un caz particular, foarte des întălnit, în care se alege un nod special, numit rădăcină. În decursul acestui capitol, dacă NU se face o altă precizare, prin denumirea de arbore vom înţelege un arbore cu rădăcină.

Fig. 1 Exemplu de arbore

 

CUPRINS:

• DEFINITII

• REPREZENTAREA ARBORILOR

• PARCURGEREA ARBORILOR

• EXEMPLE DE APLICATII

 

DEFINITII

Arbore cu rădacină= graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Descendent direct /  fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.

Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului ydacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.

Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.

Nod interior = un nod al arborelui care nu este nici rădăcină, nici frunză.

Frunză =  într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent direct

Numerotarea nodurilor este la latitudinea utilizatorului

Conform acestor definiţii, în figura de mai sus avem:

• nodul 1 este nodul rădăcină
• nodurile 10, 6, 3, 11, 8, 14 şi 13 sunt frunze
• numărul de noduri este 14 (n = 14)
• numărul de muchii este 13 (m = 13)
• nodurile 7, 8, 9, 11, 12, 13 şi 14 sunt descendenţi ai nodului 4
• nodurile 7, 8 şi 9 sunt descendenţi direcţi ai lui 9 (sunt fii ai nodului 4)
• nodurile 7, 8 şi 9 sunt fraţi; nodurile 5 şi 6 sunt fraţi
• nodurile 5, 2 şi 1 sunt ascendenţi ai nodului 10
• nodul 5 este tatăl (sau părintele) nodului 10

 

 

REPREZENTAREA GRAFURILOR NEORIENTATE

 

A. Matricea de adiacenta

Matricea de adiacenta asociată arboreluilui A = (X, M), este o matrice pătratică de ordinul n, notată ma[ ][ ], ale cărei elemente sunt definite astfel:

	01	02	03	04	05	06	07	08	09	10	11	12	13	14
01	0	1	1	1	0	0	0	0	0	0	0	0	0	0
02	1	0	0	0	1	1	0	0	0	0	0	0	0	0
03	1	0	0	0	0	0	0	0	0	0	0	0	0	0
04	1	0	0	0	0	0	1	1	9	0	0	0	0	0
05	0	1	0	0	0	0	0	0	0	1	0	0	0	0
06	0	1	0	0	0	0	0	0	0	0	0	0	0	0
07	0	0	0	1	0	0	0	0	0	0	1	0	0	0
08	0	0	0	1	0	0	0	0	0	0	0	0	0	0
09	0	0	0	1	0	0	0	0	0	0	0	1	1	0
10	0	0	0	0	1	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	1	0	0	0	0	0	0	0
12	0	0	0	0	0	0	0	0	1	0	0	0	0	1
13	0	0	0	0	0	0	0	0	1	0	0	0	0	0
14	0	0	0	0	0	0	0	0	0	0	0	1	0	0

 

 

B. Matricea muchiilor

Matricea muchiilor asociată arborelui A = (X, M), este o matrice, în general nepătratică de dimensiune m(m fiind numărul de muchii din arbore), matrice notată mm[ ][ ], ale cărei elemente sunt definite astfel:

 

	x	y
1	1	2
2	1	3
3	1	4
4	2	5
5	2	6
6	5	10
7	4	7
8	4	8
9	4	9
10	7	11
11	9	12
12	9	13
13	12	14

 

 

C. Listele de adiacenta

 

• 1: 2, 3, 4
• 2: 1, 1, 5, 6
• 3: 1
• 4: 1, 7, 8, 9
• 5: 2, 10
• 6: 2
• 7: 4, 11
• 8: 4
• 9: 4, 12, 13
• 10: 5
• 11: 7
• 12: 9, 14
• 13: 9
• 14: 12

 

D. Vectorul de taţi

Vectorul de taţi este specific arborilor; este un vector v[ ] de dimensiune n, unde n este numărul nodurilor din arbore, care păstrează pe poziţia i numărul nodului tată al nodului i.

Conceptul este foarte intuitiv, după cum se poate vedea din exemplul de mai jos:

v[i]	0	1	1	1	2	2	4	4	4	5	7	9	9	12
i	1	2	3	4	5	6	7	8	9	10	11	12	13	14

 

PARCURGEREA ARBORILOR

 

A. Parcurgerea în lăţime

Arborii fiind cazuri particulare de grafuri, nu există nici o deosebire între străbaterea în lăţime a grafurilor şi străbaterea în lăţime a arborilor

B. Parcurgerea în adâncime

Arborii fiind cazuri particulare de grafuri, nu există nici o deosebire între străbaterea în înlţime a grafurilor şi străbaterea în înălţime a arborilor

 

 

 

Up Home Structura Site

 

 

Up Home Structura Site

 

Exemplul 1:

Pentru arborele din figura 1, avem fisierul “arcgrf1.in”, cu următorul conţiunut:

14 13
1 2
1 3
1 4
2 5
2 6
5 10
4 7
4 8
4 9
7 11
9 12
9 13
12 14

se obţin rezultatele:

O variantă on-line poate fi experimentată la strabatArb

Up Home Structura Site

 

Up Home Structura Site