BAC Grafuri
BAC Grafuri
BAC Grafuri
1. Câte grafuri neorientate, distincte, cu 4 vârfuri, se pot construi? Două grafuri se consideră
distincte dacă matricele lor de adiacenţă sunt diferite.
a. 24 b. 4 c. 46 d. 26
2. Prin înălţimea unui arbore cu rădăcină înţelegem numărul de muchii ale celui mai lung lanţ
format din noduri distincte care are una dintre extremităţi în rădăcina arborelui. Scrieţi care
este înălţimea şi care sunt frunzele arborelui descris prin următorul vector ”de taţi”:
(6,6,5,0,6,4,4,7).
3. Câte grafuri neorientate, distincte, cu 8 vârfuri se pot construi? Două grafuri se consideră
distincte dacă matricele lor de adiacenţă sunt diferite.
a. 414 b. 214 c. 428 d. 64
4. Câte frunze are arborele cu rădăcină descris prin următorul vector ”de taţi”:
(6,5,5,2,0,3,3,3,8,7,7)?
a. 1 b. 2 c. 5 d. 4
6. Într-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un număr nenul. Doar
patru dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare.
Care este numărul maxim de noduri pe care poate să le aibă graful?
a. 32 b. 36 c. 10 d. 16
10. Se consideră graful neorientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi mulţimea
muchiilor {[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]}.Care este
numărul minim de muchii ce pot fi eliminate şi care sunt aceste muchii astfel încât graful
parţial obţinut să nu mai fie conex?
11. Se consideră un graf neorientat cu 50 noduri şi 32 muchii. Care este numărul maxim de
vârfuri cu gradul 0 pe care le poate avea graful?
a. 45 b. 40 c. 41 d. 50
12. Se consideră un graf neorientat cu 80 de noduri şi 3160 muchii. Care este numărul de muchii
ce pot fi eliminate astfel astfel încât graful parţial obţinut să fie arbore?
13. Câte grafuri neorientate, distincte, cu 5 vârfuri, se pot construi? Două grafuri se consideră
distincte dacă matricele lor de adiacenţă sunt diferite.
a. 54 b. 52 c. 210 d. 410
Grafuri Neorientate & Arbori
15. Care este vectorul "de taţi" pentru arborele cu rădăcină din figura
alăturată?
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
16. Scrieţi listele de adiacenţă prin care este reprezentat un exemplu de graf neorientat conex, cu
6 noduri, numerotate de la 1 la 6, care este eulerian, dar NU este hamiltonian.
17. Se consideră un graf neorientat cu 5 noduri, etichetate cu câte o literă distinctă din mulţimea
{a, b, c, d, e}, în care orice nod etichetat cu o vocală este adiacent cu toate nodurile
etichetate cu consoane şi numai cu acestea, iar orice nod etichetat cu o consoană este adiacent
numai cu nodurile etichetate cu vocale. Câte muchii are acest graf?
a. 12 b. 6 c. 4 d. 3
18. Care sunt etichetele nodurilor de tip frunză ale arborelui cu rădăcină, având 7 noduri,
numerotate de la 1 la 7, şi următorul vector “de taţi”: (5,1,5,1,0,7,5)?
19. Câţi fraţi are nodul 1 din arborele cu rădăcină, cu 7 noduri, numerotate de la 1 la 7, având
următorul vector ”de taţi”: (5,1,5,1,0,7,5)?
a. 3 b. 1 c. 0 d. 2
21. Dacă n este un număr natural impar mai mare decât 2, atunci 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 niciunciclu)
22. Care este gradul maxim posibil şi care este gradul minim posibil pentru un nod dintr-un
arbore cu n noduri (n>1)?
23. 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 poate fi numărul maxim de noduri terminale
(frunze) ale arborelui în acest caz?
24. 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
Grafuri Neorientate & Arbori
25. 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?
26. Î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? Scrieţi pentru fiecare dintre aceste subgrafuri nodurile din care este
format.
27. 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)?
28. 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
29. 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
31. 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
32. 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?
a. 1 b. 3 c. 2 d. 5
33. Î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?
a. 8 b. 9 c. 10 d. 6
34. 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
35. Î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
Grafuri Neorientate & Arbori
36. 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
37. Care sunt nodurile de tip frunză din arborele alăturat dacă se alege ca
rădăcină nodul 6?
42. Un arbore cu rădăcină are nodurile numerotate de la 1 la 18 şi este reprezentat prin vectorul
de „taţi” t=(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numărul tuturor
descendenţilor nodului 3 este egal cu:
a. 3 b. 6 c. 17 d. 18
43. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile: [1,60],
[60,20], [2,30] şi [4,30]. Numărul componentelor conexe ale grafului este egal cu:
a. 3 b. 56 c. 54 d. 0
44. Într-un arbore cu rădăcină, cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rădăcină,
iar între celelate noduri există relaţia: nodul cu numărul i+1 este tatăl celui cu numărul i,
pentru i∈{1,2,3,4,5,6,7,8,9}. Vectorul de „taţi” al arborelui astfel definit, este:
a. (0,1,2,3,4,5,6,7,8,9) b. (1,2,3,4,5,6,7,8,9,0)
c. (2,3,4,5,6,7,8,9,10,0) d. (9,8,7,6,5,4,3,2,1,0)
48. Câte muchii trebuie eliminate dintr-un graf neorientat complet cu 20 de noduri, pentru ca
graful parţial obţinut să fie arbore?
50. Stabiliţi care dintre următorii vectori este vector de ”taţi” pentru 0 1 0 0 1 0 0
arborele cu 7 noduri, numerotate de la 1 la 7, cu rădăcina 1, reprezentat 1 0 1 1 0 0 0
prin matricea de adiacenţă alăturată: 0 1 0 0 0 0 0
a. (1, 0, 2, 2, 1, 5, 5) 0 1 0 0 0 0 0
b. (0, 1, 2, 2, 1, 5, 5) 1 0 0 0 0 1 1
c. (3, 1, 0, 2, 1, 5, 6) 0 0 0 0 1 0 0
d. (2, 1, 0, 2, 1, 5, 2) 0 0 0 0 1 0 0
52. Se consideră vectorul de ”taţi" al unui arbore cu rădăcină t=(3,4,0,3,3,5) ale cărui
noduri sunt numerotate de la 1 la 6. Alegeţi afirmatia corectă:
a. nodurile 4 şi 6 sunt noduri de tip frunză
b. nodul 3 are un singur descendent direct (fiu)
c. nodul 6 este tatăl nodului 5
d. nodurile 1, 2, 6 sunt noduri de tip frunză
59. Pentru reprezentarea unui arbore cu rădăcină, cu 10 noduri, etichetate cu numerele naturale
de la 1 la 10, se utilizează vectorul de “taţi”: TATA = (4, 8, 8, 0, 10, 4, 8, 6, 2,
6). Care este rădăcina arborelui şi câte frunze are acesta?
62. Graful neorientat G este dat prin matricea de adiacenţă alăturată. Câte 0 0 0 0 1
vârfuri ale grafului G au gradul 1? 0 0 1 1 0
a. 1 b. 2 c. 3 d. 0 0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
63. Pentru reprezentarea unui arbore cu rădăcină, cu 9 noduri, etichetate cu
numerele naturale de la 1 la 9, se utilizează vectorul de „taţi”: T = (2,0,1,7,3,1,2,4,1).
Care sunt descendenţii direcţi ai rădăcinii şi câte frunze are arborele dat?
64. Care dintre următoarele propoziţii este falsă pentru graful orientat G, dat
0 1 1 0 0
prin matricea de adiacenţă alăturată? 0 0 1 1 0
a. există cel puţin un nod în graful G care are gradul intern egal cu cel extern 0 0 0 1 1
b. graful G nu are circuite 1 1 0 0 0
c. există cel puţin un drum între oricare două noduri ale grafului G 0 0 0 1 0
d. graful G are 9 arce
Grafuri Neorientate & Arbori
65. Care sunt nodurile de tip frunză ale arborelui cu rădăcină cu 9 noduri, numerotate de la 1 la
9, al cărui vector „de taţi” este (6, 6, 8, 8, 7, 7, 0, 7, 7)?
66. Care dintre următorii vectori NU poate reprezenta vectorul „de taţi” al unui arbore cu
rădăcină, cu 5 noduri, numerotate de la 1 la 5?
a. 3 1 0 1 2 b. 2 0 1 1 2 c. 3 4 0 2 3 d. 4 1 1 0 2
67. Care este numărul de circuite distincte ale grafului orientat dat prin 0 0 1 0 0 0
matricea de adiacenţă alăturată? Două circuite sunt distincte dacă diferă 1 0 1 0 1 1
prin cel puţin un arc. 0 0 0 0 0 0
a. 0 b. 1 c. 2 d. 3 0 0 1 0 0 0
0 0 0 0 0 0
68. Care dintre nodurile arborelui din figura alăturată pot fi considerate ca 0 0 0 1 1 0
fiind rădăcină astfel încât în arborele cu rădăcină rezultat fiecare nod să
aibă cel mult doi descendenţi direcţi?
70. Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3
componente conexe?
71. Se consideră graful neorientat din figura alăturată. Care este numărul
minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă
exact 3 componente conexe?
a. 2 b. 4 c. 1 d. 3
72. Se consideră un graf orientat cu 5 vârfuri şi 8 arce. Care dintre următoarele şiruri de numere
poate fi şirul gradelor exterioare ale vârfurilor acestui graf?
a. 2, 3, 1, 1, 1 b. 2, 2, 6, 5, 1
c. 1, 0, 1, 1, 1, 1 d. 1, 1, 0, 2, 1
73. Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri, care
nu este conex?
a. 4 b. 15 c. 12 d. 10
74. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin
următorul vector „de taţi”: (4,1,6,0,1,1,4,7). Care sunt frunzele arborelui?
75. Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri
şi 6 muchii?
a. G are cel puţin un ciclu
b. G este conex
c. G are gradele tuturor nodurilor numere pare
d. G nu poate avea noduri cu gradul 0
76. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin
următorul vector „de taţi”: (3,5,0,3,3,5,5,5).
a) Care este nodul cu cei mai mulţi descendenţi direcţi (fii)?
b) Care sunt nodurile frunză ale acestui graf?
Grafuri Neorientate & Arbori
77. Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci
numărul maxim de componente conexe pe care le poate avea graful este:
a. 2 b. 4 c. 3 d. 5
78. Fie n un număr natural, n>4. Orice graf neorientat cu n noduri şi n muchii:
a. are gradele tuturor nodurilor numere pare b. este conex
c. are cel puţin un ciclu d. este arbore
79. Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris
prin următorul vector „de taţi”: (4,5,0,3,4,5,4,5). Care sunt frunzele arborelui?
80. Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel mult:
a. 28 de muchii b. 12 muchii c. 21 de muchii d. 16 muchii
81. Dacă T este un arbore cu rădăcină, cu 100 de noduri, care este numărul minim de frunze pe
care le poate avea T?
87. Care este numărul minim de muchii care trebuie adăugate grafului
alăturat pentru a deveni conex şi eulerian?
88. Care este numărul de noduri ale unui arbore cu 100 de muchii?
89. Se consideră graful neorientat definit prin mulţimea nodurilor {1,2,3,4,5,6} şi muchiile
[1,2],[1,3],[2,3],[6,5],[3,4],[4,5],[4,6]. Care este numărul maxim de
muchii care pot fi eliminate din graf pentru a se obţine un graf parţial al său care să fie conex?
a. 1 b. 2 c. 0 d. 3
92. Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura
alăturată în care nodul 5 este nodul rădăcină?
93. Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura
alăturată în care nodul 1 este nodul rădăcină?
94. Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura
alăturată în care nodul 5 este nodul rădăcină?
97. Se consideră arborele cu 12 noduri, numerotate de la 1 la 12, definit prin următorul vector
„de taţi”: (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
102. Care este numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21
noduri şi 20 muchii?
103. Care este numărul minim de muchii ale unui graf neorientat conex, cu 100 de noduri?
107. Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea
nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4],
[3,4], [4,5]}?
a. Este graf hamiltonian, dar nu este eulerian.
b. Este graf eulerian, dar nu este hamiltonian.
c. Este şi graf hamiltonian şi graf eulerian.
d. Nu este graf hamiltonian, şi nici nu este graf eulerian.
110. Scrieţi matricea de adiacenţă a unui graf neorientat cu 6 noduri în care toate nodurile au
gradul 2 şi care are două componente conexe.
121. Care este numărul minim de noduri ce trebuie eliminate din graful
alăturat astfel încât subgraful obţinut să nu fie conex?
a. 3 b. 0 c. 2 d. 1