Test Grila Teoria Grafurilor
Test Grila Teoria Grafurilor
Test Grila Teoria Grafurilor
5. Numărul minim de muchii ale unui graf neorientat, conex, cu 10 de noduri, este: (4p.)
a. 5 b. 9 c. 10 d. 45
7. Se consideră un graf orientat cu 100 de vârfuri, fiecare dintre acestea având atât gradul
interior cât si gradul exterior egale cu 99. Numărul maxim de arce care pot fi eliminate din graf
astfel încât, în graful parțial obținut, între oricare două vârfuri să existe cel puțin un arc, este:
(4p.)
a. 9801 b. 4950 c. 900 d. 50
8. Se consideră un graf orientat cu 6 vârfuri şi fără circuite. Numărul maxim de arce al grafului
este: (4p.)
a. 5 b. 7 c. 10 d. 15
9. Se consideră un arbore cu 5 noduri, dintre care doar trei au gradul egal cu 1. Scrieţi două
valori care să reprezinte gradele celorlalte două noduri. (6p.)
10. Într-un arbore cu rădăcină considerăm că un nod se află pe nivelul x dacă lanțul elementar
care are o extremitate în nodul respectiv si cealaltă extremitate în rădăcina arborelui are
lungimea x. Pe nivelul 0 se află un singur nod (rădăcina).
Se consideră un arbore cu rădăcină, cu patru niveluri. Toate nodurile de pe acelasi nivel
(cu excepția ultimului nivel) au un număr egal (nenul) de descendenți direcți („fii”) si nu există
două niveluri cu acelasi număr de noduri. Numărul minim de noduri de pe nivelul 3 este:
(4p.)
a. 6 b. 8 c. 9 d. 12
12. Se consideră un graf neorientat complet, cu 9 noduri. Pentru a obține un graf parțial al său
cu două componente conexe, fiecare dintre acestea fiind grafuri complete, numărul maxim de
muchii care pot fi eliminate este:
(4p.)
a. 14 b. 18 c. 20 d. 24
12. Un arbore cu 37 de noduri, numerotate de la 1 la 37, are ca rădăcină nodul numerotat cu 1,
iar tatăl fiecărui nod i (i є [2,37]) este numerotat cu partea întreagă a rădăcinii pătrate a lui i (
[ √ i ]). Numărul de frunze ale arborelui este: (4p.)
a. 36 b. 31 c. 21 d. 6
13. Un graf neorientat cu 8 noduri, numerotate de la 1 la 8, are muchiile [1,2], [1,6], [4,6],
[3,6], [6,5], [5,3], [3,4], [7,8], [8,2]. Enumerați trei noduri care nu aparţin niciunui ciclu în
acest graf. (6p.)
17. Câte grafuri orientate cu 5 vârfuri, dintre care unul este izolat există? (4p.)
a) 10*211; b) 10*25; c) 212; d) nu poate fi precizat.
19. Câte grafuri orientate, distincte, cu 4 vârfuri se pot construi? Două grafuri se consider
distincte dacă matricele lor de adiacenţă sunt diferite. (4p.)
a. 46 b. 26 c. 64 d. 4
20. Care dintre secvenţele următoare de numere pot reprezenta şirurile gradelor
exterioare şi interioare ale unui graf orientat? (4p.)
a) gr_ext=(1,1,1,0,1,2) gr_int=(0,2,2,1,0,0)
b) gr_ext =(6,0,1,1,0,0) gr_int=(0,2,2,2,2,0)
c) gr_ext=(1,1,1,1,1,1) gr_int=(6,0,0,0,0,0)
d) gr_ext=(1,1,1,0,1,1) gr_int=(0,2,2,1,0,0)
21. Câte grafuri orientate cu 5 vârfuri, dintre care două sunt izolate există? (4p.)
22. O cunoştinţă mi-a zis: la mine în birou suntem 5 persoane. Fiecare dintre noi colaborează cu
exact 3 persoane. A zis adevărul? Justificați răspunsul!
11A – Teoria grafurilor