Probleme rezolvate 2

Probleme realizate de catre :

• Constantinescu Florin
• Totoc Traian
• Tigau Adrian

Varianta 16
1.  Dacă n este un număr 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 conţine niciun
ciclu)
             Raspuns: b. graf eulerian
Varianta 17
3. Care este gradul maxim posibil şi care este gradul minim posibil pentru un nod dintr-un arbore cu n noduri?
       

Raspuns : Gradul maxim este 4,iar gradul minim este 1

Varianta 18

3. Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult 2 descendenţi direcţi (fii). Înălţimea unui arbore este reprezentată de numărul maxim de muchii ale unui lanţ elementar ce uneşte rădăcina cu un vârf terminal (frunză).
Pentru un arbore binar cu exact 8 noduri, care este înălţimea minimă posibilă şi care este numărul de noduri terminale (frunze) în acest caz?

        Raspuns:  Inaltimea minima este 3 ,iar numarul de frunze este 4

Varianta 19

1. Un graf neorientat este complet dacă oricare două noduri distincte ale sale sunt adiacente. Care este numărul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7 noduri, astfel încât graful parţial obţinut să fie arbore?
a. 15      
b. 1
c. 6
d. 21
Raspuns: a. 15

Varianta 20

1. Matricea de adiacenţă a unui graf neorientat G are numărul valorilor de 1 egal cu jumătate din numărul valorilor de 0. Care dintre numerele de mai jos poate fi numărul de noduri ale grafului G?
a. 12
b. 14
c. 11
d. 13

Raspuns: a. 12

Varianta 21

2. Într-un graf orientat cu 7 noduri suma gradelor interioare ale tuturor nodurilor este egală cu 10. Care este valoarea sumei gradelor exterioare ale tuturor nodurilor?
a. 5
b. 20
c. 10
d. 1

Raspuns:    c. 10                  

Varianta 22

4. Într-un graf neorientat cu 10 noduri, numerotate de la 1 la 10, există câte o muchie între oricare două noduri numerotate cu numere consecutive şi câte o muchie între nodul numerotat cu 10 şi fiecare dintre celelalte noduri. Câte subgrafuri cu exact 3 noduri, toate adiacente două câte două, are graful dat?

Raspuns: 8       

Varianta 23

3. Care sunt nodurile care au exact 2 descendenţi pentru un arbore cu rădăcină, cu 7 noduri, numerotate de la 1 la 7, dat de vectorul de ”taţi”: (3,3,0,1,2,2,4)?

Raspuns: 2,3        








Varianta 24

2. Care din următoarele proprietăţi este adevărată pentru un graf orientat cu n vârfuri şi n arce (n>3) care are un circuit de lungime n:
a. există un vârf cu gradul n-1
b. pentru orice vârf gradul intern şi gradul extern sunt egale
c. graful nu are drumuri de lungime strict mai mare decât 2
d. gradul intern al oricărui vârf este egal cu 2

Raspuns:  b. pentru orice vârf gradul intern şi gradul extern sunt egale

Varianta 25

2. Un graf neorientat cu 8 noduri are gradele nodurilor egale cu 1,2,4,2,3,2,1,x. Pentru
ce valoare a lui x graful este arbore?
a. x=1
b. x<3
c. x>3
d. nicio valoare

Raspuns: d. nicio valoare

Varianta 26

1. Pentru graful neorientat din figura alăturată, care este numărul de
muchii ale celui mai lung lanţ, format din noduri distincte, ce are
ca extremităţi nodurile 1 şi 3?
a. 2   b. 3 c. 1 d. 4
Raspuns: d. 4 (1,2,4,5,3)



2. Care este nodul ce poate fi ales ca rădăcină a arborelui din figura
alăturată, astfel încât fiecare nod care nu este de tip frunză să aibă
un număr impar de descendenţi direcţi (fii) ?
a. 3 b. 4 c. 6 d. 1

Raspuns:  c. 6

Varianta 27

1. Care este numărul minim de arce ce trebuie adăugate în graful orientat
din figura alăturată astfel încât fiecare vârf să aparţină unui circuit ?

a. 1 b. 2 c. 3 d. 4
Raspuns: a. 1

2. Care este numărul nodurilor de tip frunză din arborele cu rădăcină, cu 8 noduri, numerotate de la 1 la 8, reprezentat prin vectorul ”de taţi” (2,0,6,2,4,4,5,5)?
a. 3 b. 4 c. 5 d. 2

Raspuns: b. 4









Varianta 28

1. Care este numărul minim de muchii ce pot fi eliminate din graful
alăturat astfel încât în graful parţial rezultat să existe exact un vârf de
grad 0? (6p.)
a. 1 b. 3 c. 2 d. 5

Raspuns: b. 3

2. Într-un arbore cu rădăcină nivelul unui nod este egal cu lungimea lanţului format din noduri distincte care uneşte rădăcina cu acel nod. Rădăcina se află pe nivelul 0. Dacă toate frunzele se află pe nivelul 3 şi oricare nod neterminal aflat pe un nivel k are exact k+1 descendenţi direcţi (fii), care este numărul de noduri din acest arbore ? (4p.)
a. 8 b. 9 c. 10 d. 6

Raspuns: c. 10  

Varianta 29

1. Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri?
a. 4 b. 5 c. 3 d. 2

Raspuns: a. 4  




2. Într-un arbore cu rădăcină nivelul unui nod este egal cu lungimea lanţului
format din noduri distincte care uneşte rădăcina cu acel nod. Care dintre
noduri trebuie ales ca rădăcină în arborele din figura alăturată astfel încât
pe fiecare nivel să se găsească un număr impar de noduri?
a. 2 b. 3 c. 6 d. 4

Raspuns: d. 4

Varianta 30

1. Care este numărul minim de muchii ce trebuie mutate în graful din
figura alăturată astfel încât acesta să fie conex şi fiecare nod să
aparţină unui ciclu?
a. 0 b. 1 c. 2 d. 3

Raspuns: b. 1

3. Care sunt nodurile de tip frunză din arborele alăturat dacă se alege ca
rădăcină nodul 6?

Raspuns: 5,4,3,2



Varianta 31

1. Se consideră graful neorientat cu 7 noduri, numerotate de la 1 la 7, şi muchiile[1,3], [2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre următoarele succesiuni de noduri reprezintă un lanţ care trece o singură dată prin toate nodurile grafului?
a. (1, 2, 3, 4, 5, 6, 7) b. (4, 5, 3, 6, 7)
c. (7, 6, 3, 5, 4, 2, 1) d. (1, 3, 5, 4, 2, 3, 6)

Raspuns: c. (7, 6, 3, 5, 4, 2, 1)  

2. Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului de taţi t=(2,5,5,3,0,2,4,6,6,2,3). Mulţimea tuturor ascendenţilor nodului 8 este:
a. {1, 2, 5, 6, 10} b. {6, 2, 5} c. {6} d. {5, 2}

Raspuns: b. {6, 2, 5}

Varianta 32

1. Un graf orientat este memorat cu ajutorul listelor de
adiacenţă scrise alăturat. Nodurile care au gradul exterior
egal cu 2 sunt: 1:(5,6) 2:(1,5,4) 3:(1,5) 4:(1,2) 5:(2) 6:(2,4,5)
a. 2 şi 5 b. 1,3 şi 4 c. 6 d. 2 şi 3

Raspuns: b. 1,3 şi 4




2.Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este
reprezentat cu ajutorul matricei de adiacenţă alăturate. Pentru acest
graf este adevărată afirmaţia:
a. Graful este hamiltonian b. Graful nu are noduri de grad 0
c. Gradul maxim al unui nod este 3 d. Graful are trei componente conexe

Raspuns: d. Graful are trei componente conexe