ARBORI-Probleme propuse

ARBORI-Probleme propuse

1) S? se creeze arborele genealogic personal pe parcursul a trei sau patru generaii, pun?ndu-se ?n nodul r?d?cin? prenumele propriu, iar ca descendeni ai fiec?rui nod, numele p?rinilor. (Se va obine un arbore genealogic asem?n?tor cu cel ?n accepiune clasic?, dei noiunile de str?mo i urma au fost inversate).

2) Se consider un arbore cu 11 muchii. Care este numrul de noduri ale arborelui?

3) Dac G este un graf neorientat cu proprietatea c ?ntre orice dou v?rfuri ale sale exist un unic lan elementar, atunci G este: a. graf eulerian b. arbore c. graf hamiltonian d. un graf cu toate gradele numere impare

4) Numrul minim de muchii care pot fi eliminate astfel ?nc?t graful din desenul alturat s? devin arbore este:

5) Un graf neorientat cu n noduri, cu n numr impar mai mare dec?t 2, ?n care fiecare nod are gradul n-1, este ?ntotdeauna: a. graf aciclic (graf care nu conine nici un ciclu) b. arbore c. graf neconex d. graf eulerian

6) Se consider graful neorientat reprezentat prin matricea de adiacen 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 atunci graful este a. eulerian b. aciclic c. arbore d. Hamiltonian

7) Precizai dac este arbore graful G(X, U) definit astfel: X={1,2,3,4,5,6,7,8,9,10} U={[1,2], [1,3], [1,5], [2,6], [2,7], [3,4], [3,9], [4,8], [8,10] }.

8) Dac nodul cu eticheta 2 are patru frai, iar nodul cu eticheta 1 este printele lui, ce ordin are nodul cu eticheta 1?

1

9) Demonstrai c un arbore este un graf bipartit. Reciproca este adevrat? 10) Un arbore cu rdcin A(X, U) este definit astfel: X={1,2,3,4,5,6,7,8,9,10} U={[1,2], [1,3], [1,4], [2,6], [3,5], [3,7], [3,9], [4,8], [8,10] }. Precizai: a) dac eticheta nodului rdcin este 1, c?te frunze are arborele i care sunt aceste frunze; b) dac eticheta nodului rdcin este 2, c?i frai are nodul cu eticheta 1 i pe ce nivel se gsete nodul cu eticheta 10; c) dac eticheta nodului rdcin este 10, ce ?nlime are arborele, cine este printele nodului cu eticheta 1 i care sunt fiii nodului cu eticheta 3. 11) Reprezentai sub forma vectorului tat arborele cu rdcin A5 din figura de mai jos

12) Desenai 5 arbori binari cu trei noduri (etichetate cu A, B i C) diferii, alii dec?t cei din figura de mai jos.

2

13) Se consider un arbore cu urmtoarele proprieti: rdcina este nodul 1 (considerat de nivel 1) i fiecare nod i (cu 1i3) aflat pe nivelul j are ca descendeni nodurile i+j i i+2*j. Nodurile i (cu i>3) sunt noduri terminale (frunze). Stabilii care dintre vectorii urmtori este vectorul de tai (sau de predecesori) corespunztor arborelui: a. 0 1 2 2 1 3 3 b. 0 -1 1 -1 -1 1 1 c. 0 1 1 2 3 2 3 d. 0 1 1 2 2 3 3

14) Se consider arborele din figura alturat. Care dintre noduri trebuie ales ca rdcin astfel ?nc?t ?nlimea arborelui s fie minim. a. 7 b. 3 c. 5 d. 6

15) Se consider arborele din figura alturat.. Definim ?nlimea arborelui ca fiind numrul maxim de muchii care formeaz un lan care unete rdcina de un nod terminal. Care este ?nlimea maxim a arborelui cu rdcin ce se poate obine aleg?nd ca rdcin unul dintre noduri? a. 5 b. 3 c. 6 d. 7

16) Stabilii care dintre grafurile alturate este arbore:

17) Se consier arborele cu rdcin cu 8 noduri, cu muchiile [1,7], [1,8], [3,1], [3,4], [3,5], [4,2], [4,6] i cu rdcina ?n nodul cu eticheta 3. a) Vectorul tat al arborelui este: a. 3 4 0 3 3 4 1 2 b. 3 3 0 4 3 4 1 1 c. 3 4 0 3 3 4 1 1 d. 3 4 3 3 4 1 1 0 b) Numrul de noduri terminale ale arborelui este: a. 6 b.4 c. 5 d. 3 c) ?nlimea maxim pe care o poate avea, schimb?ndu-se nodul, rdcin este: a. 6 b. 5 c. 4 d. 3 d) Dac se ia ca rdcin nodul cu eticheta 2, ?nlimea arborelui este: a. 5 b. 2 c. 4 d. 3 e) Numrul de componente conexe care se obin dac se elimin muchiile care au o extremitate ?n nodul cu eticheta 3 este: a. 3 b. 4 c. 2 d. 1

3

18) Se consider un arbore cu rdcin ?n care orice nod care nu este terminal are exact 3 descendeni direci. Atunci, numrul de noduri terminale (frunze) poate fi: a. 15 b. 24 c. 2 d. 14

19) Se consider un arbore ?n care rdcina este considerat de nivelul 1 i orice nod de pe nivelul i are exact i+1 descendeni direci, cu excepia nodurilor de pe nivelul 4 care sunt noduri terminale. Numrul de noduri terminale (frunze) sunt: a. 24 b. 120 c. 6 d. 30

20) Se consider un arbore. Despre un lan care unete dou noduri distincte n1 i n2 se poate afirma: a. este unic oricare ar fi n1 i n2 b. este unic dac i numai dac n1 sau n2 este terminal c. nu este unic oricare ar fi n1 i n2 d. este unic dac i numai dac n1 sau n2 este rdcin

21) Urmtorii 5 itemi se refer la arborele cu rdcin cu 8 noduri care are vectorul tat: 2 0 2 1 1 1 3 3. i) Numrul de noduri terminale ale arborelui este: a. 3 b.4 c. 5 d. 2 ii) Numrul de lanuri de lungime 3 este: a. 3 b.4 c. 5 d. 6 iii) Numrul de lanuri de lungime 2 care pornesc din rdcin este: a. 2 b.4 c. 3 d. 5 iv) Numrul de nivele ale arborelui este: a. 2 b.3 c. 4 d. 5 v) Fiii nodului 3 sunt: a. 4, 5, 6 b. 1, 2 c. 7, 8 d. 2, 7, 8

22) Un arbore are 14 noduri. At?t rdcina, c?t i fiecare dintre nodurile neterminale au cel mult 3 descendeni direci. ?nlimea maxim a arborelui (numrul maxim de muchii ce leag rdcina de o frunz) este: a. 4 b. 13 c. 5 d. 3

23) Numrul de muchii ale unui arbore cu 9 noduri este: a. 9 b. 7 c. 8 d. 10

24) Numrul maxim de noduri terminale ale unui arbore cu rdcin cu 15 noduri este: a. 15 b. 14 c. 12 d. 10

25) Se consider? un arbore pentru care vectorul de tai este: TATA = (2, 0, 2, 5, 2, 5). Determinai num?rul de niveluri al arborelui.

26) C?te frunze are arborele cu rdcin descris prin urmtorul vector "de tai": 1 2 3 4 5 6 7 8 9 10 11 (6,5,5,2,0,3, 3,3,8, 7, 7) a. 1 b. 2 c. 5 d. 4

4

27) Un arbore binar este un arbore cu rdcin ?n care fiecare nod are cel mult 2 descendeni direci (fii). ?nlimea unui arbore este reprezentat de numrul maxim de muchii ale unui lan elementar ce unete rdcina cu un v?rf terminal (frunz). Pentru un arbore binar cu exact 8 noduri, care este ?nlimea minim posibil i care este numrul de noduri terminale (frunze) ?n acest caz?

28) Se consider graful neorientat G cu 5 noduri reprezentat prin matricea de adiacen alturat. Stabilii care dintre afirmaiile urmtoare este adevrat: 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 a. Graful G este eulerian. b. Graful G conine dou componente conexe. c. Orice subgraf al lui G, format din 3 noduri, este arbore. d. Graful G este hamiltonian.

29) Prin ?nlimea unui arbore cu rdcin ?nelegem numrul de muchii ale celui mai lung lan format din noduri distincte care are una dintre extremiti ?n rdcina arborelui. Scriei care este ?nlimea i care sunt frunzele arborelui descris prin urmtorul vector "de tai": 1 2 3 4 5 6 7 8 (6,6,5,0,6,4,4,7).

30) Se consider un arbore cu 11 muchii. Care este numrul de noduri ale arborelui?

31) Care este vectorul "de tai" pentru arborele cu rdcin din figura alturat? a. 0 0 5 7 6 5 1 b. 1 0 0 7 6 5 0 c. 7 4 5 0 4 5 4 d. 7 4 5 0 4 5 7

32) Dac n este un numr impar mai mare dec?t 2, un graf neorientat cu n noduri, ?n care fiecare nod este adiacent cu exact n-1 noduri, este ?ntotdeauna : a. arbore b. graf eulerian c. graf neconex d. graf aciclic (graf care nu conine niciun ciclu)

33) Care este gradul maxim posibil i care este gradul minim posibil pentru un nod dintr-un arbore cu n noduri?

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download