1

1. Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descries prin urmtorul vector de tai: (4,1,6,0,1,1,4,7). Care sunt frunzele arborelui? 2.Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descries prin urmtorul vector de tai:(3,5,0,3,3,5,5,5). Care este nodul cu cei mai muli descendeni direci (fii)?

3.Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descries prin urmtorul vector de tai: (4,5,0,3,4,5,4,5). Care sunt frunzele arborelui?

4.Dac T este un arbore cu rdcin cu 100 de noduri, care este numrul minim de frunze pe care le poate avea T?

5.Se consider un arbore cu rdcin, cu 100 noduri, numerotate de la 1 la 100. Dac nodul 13 are exact 14 frai i nodul 100 este tatl nodului 13, care este numrul total de descendeni direci(fii) ai nodului 100?

6.Se consider un arbore G, cu rdcin, memorat cu ajutorul vectorului de tai urmtor:

T=(2,0,4,2,4,7,2). Care dintre urmtoarele afirmaii este adevrat? a. Nodurile 1,4 i 6 sunt frai.

b. G este conex i prin eliminarea unei muchii oarecare din G, graful obinut nu este conex.

c. Prin eliminarea muchiei [6,7] se obine un graf parial, conex.

d. Arborele G are 5 frunze.

7. Care este numrul de noduri ale unui arbore cu 100 de muchii?

8. Un arbore cu rdcin avnd 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tai t=(2,5,5,3,0,2,4,1,1). Scriei toi ascendenii nodului 4.

9. Un arbore cu rdcin avnd 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de tai t=(8,8,0,3,4,3,4,6). Scriei care este numrul total de descendeni ai nodului 4.

10. Care este vectorul de tai asociat arborelui cu rdcin din figura alturat? (6p.) 11. Care este vectorul de tai asociat arborelui cu rdcin din figura alturat?

12. Care este vectorul de tai asociat arborelui cu rdcin din figura alturat?

13. Fie un arborele cu rdcin cu 9 noduri, numerotate de la 1 la 9. Care este vectorul de tai al acestui arbore tiind c nodurile 1, 2, 3, 4 ,5, 6, 7, 8 au exact cte un descendent direct (fiu)?

a. (1,2,3,4,5,6,7,8) b. (1,2,3,4,5,6,7,8,9)

c. (0,1,2,3,4,5,6,7,8) d. (0,1,2,3,4,5,6,7,8,9)

14. Se consider arborele cu 12 noduri, numerotate de la 1 la 12, definit prin urmtorul vector de tai: (4, 8, 0, 3, 10, 1, 8, 3, 2, 4, 7, 10). Care dintre nodurile arborelui au exact un descendent direct (fiu)?

a. 6, 9, 11 b. 1, 2, 7 c. 5, 12, 6, 9, 11 d. 10, 1, 2, 7

15. Se consider un arbore cu 9 noduri, numerotate de la 1 la 9, i cu vectorul de tai urmtor: (8, 8, 8, 2, 6, 2, 9, 0, 2).

a) Enumerai descendenii nodului 2. b) Cte noduri de tip frunz are acest arbore?

16. Fie graful orientat cu 8 vrfuri, numerotate de la 1 la 8, i arcele (1,2), (2,3), (3,1),(4,5), (5,6), (5,7), (6,7), (7,4), (8,7). Care este numrul minim de arce care trebuie adugate astfel nct, pentru oricare dou vrfuri x i y din graf s existe cel puin un drum de la nodul x la nodul y?

17. Care este vectorul de tai pentru arborele cu 8 noduri, numerotate de la 1 la 8, i muchiile[1,5], [2,3], [3,6], [3,8], [4,6], [5,7], [6,7], dac se alege ca rdcin nodul numerotat cu 6?

18. Se consider arborele cu 13 noduri, numerotate de la 1 la 13,i mulimea muchiilor

{[1,4], [2,5], [3,8], [4,7], [4,9], [4,11], [6,3], [6,10], [6,12], [5,6],

[13,2], [2,9]}. Dac se alege nodul notat cu 2 drept rdcin, care este vectorul de

tai pentru acest arbore?

19. Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tai t=(9,3,4,7,3,9,0,7,2). Mulimea tuturor nodurilor de tip frunz este:

a. {8, 6, 1, 5} b. {1, 6} c. {8} d. {1, 6, 8}

20. Scriei matricea de adiacen a arborelui cu 6 noduri, numerotate de la 1 la 6, definit prin urmtorul vector "de tai": (0, 1, 1, 1, 3, 3).21. Se consider un arbore cu 6 noduri, numerotate de la 1 la 6,reprezentat prin matricea de adiacen dat alturat. Scriei toate nodurile care pot fi alese ca rdcin a arborelui astfel nct acesta s aib un numr maxim de frunze.

0 1 0 0 0 1

1 0 1 1 1 0

0 1 0 0 0 0

0 1 0 0 0 0

0 1 0 0 0 0

1 0 0 0 0 0

22. Determinai ultima valoare (notat cu ?) din vectorului de tai (0, 1, 1, 2, 3, 3, ?) astfel nct arborele cu 7 noduri, numerotate de la 1 la 7, descris de acest vector, s aib pe fiecare nivel n exact 2n noduri, nodul rdcin fiind pe nivelul n=0, i fiecare nod s aib cel mult doi descendeni. Scriei matricea de adiacen a arborelui astfel definit.

23. Se consider un arbore cu 6 noduri, numerotate de la 1 la 6, reprezentat prin matricea de adiacen dat alturat. Scriei toate nodurile care pot fi alese ca rdcin a arborelui astfel nct acesta s aib un numr par de frunze. 0 1 0 0 0 1

1 0 1 1 1 0

0 1 0 0 0 0

0 1 0 0 0 0

0 1 0 0 0 0

1 0 0 0 0 0

24. Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului de tai t=(2,5,5,3,0,2,4,6,6,2,3). Descendenii direci (fiii) ai nodului 2 sunt:

a. 1, 6 i 10 b. 5 c. 6, 8 i 9 d. 325. Scriei vectorul de tai corespunztor arborelui cu 8 noduri,numerotate de la 1 la 8, dat prin lista alturat adescendenilor direci (fiilor)?

1: 4,6,7

2: -

3: 1,8

4: -

5: -

6: 2

7: -

8: 5

26. Se consider arborele din figura alturat. Care este nodul care trebuie ales ca rdcin astfel nct vectorul de tai corespunztor arborelui rezultat s conin patru elemente egale?

27. Un graf cu 5 noduri, numerotate de la 1 la 5, conine urmtoarele muchii: [1,2], [1,3],[2,3], [2,5], [3,4], [3,5], [4,5]. Eliminai din acest graf numrul necesar de muchii astfel nct graful parial rezultat s fie arbore. Considernd c acest arbore are ca rdcin vrful 5, care este vectorul cu legturi de tip tat corespunztor ?

28. Cte valori nule pot s apar ntr-un vector cu legturi de tip tat asociat unui arbore cu rdcin care conine 10 noduri?

a. niciuna b. exact una c. depinde de configuraia arborelui d. exact dou

29. Care este numrul maxim de valori egale care pot s apar ntr-un vector cu legturi de tip tat asociat unui arbore cu rdcin care conine 10 noduri? a. cel mult 2 b. 10 c. nu pot s apar valori egale ntr-un vector cu legturi de tip tat d. 9

30.Se consider un arbore cu rdcin memorat cu ajutorul vectorului de tai

T=(2,0,1,1,1,2). Stabilii care dintre nodurile arborelui sunt situate pe nivelul 3, dacrdcina este situat pe nivelul 1?

a. 3 4 5 b. 1 c. 2 6 d. 1 2 6

31. Scriei vectorul de tai al unui arbore cu rdcin, tiind c:

nodurile arborelui sunt numerotate cu numerele naturale distincte 1, 2, 3, ...;

numrul nodurilor este 4 sau 6;

nodul 1 este desemnat ca rdcin;

numrul nodurilor de tip frunz este egal cu jumtate din numrul total de noduri din arbore;

numrul de nivele pe care sunt dispuse nodurile arborelui este egal cu numrul nodurilor de tip frunz.

32.Se consider arborele cu 6 noduri, numerotate de la 1 la 6, cu muchiile [2,1], [2,4], [4,5], [6,2], [6,3]. Scriei toate nodurile desemnate ca rdcin astfel nct fiecare arbore cu rdacin obinut s aib exact 3 frunze.