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. Câte grafuri neorientate, distincte, cu 8 vârfuri se pot construi? Două grafuri se consideră distincte dacă matricele lor de
adiacenţă sunt diferite. (4p.)
a.414 b. 214 c. 428 d. 64
3. Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii
divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte?
a. 6 b. 5 c. 3 d. 4
4. Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor
formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii
divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte,
ce uneşte nodul 6 cu nodul 1? (4p.)
a. 1 b. 3 c. 4 d. 6
5. Se consideră un graf neorientat G cu 12 noduri si 7 muchii. Care este numărul maxim de componente conexe din care
poate fi format graful G?
6. 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? (6p.)

7. Se consideră graful orientat cu 6 noduri reprezentat prin matricea de adiacenţă alăturată. Care este numărul tuturor
grafurilor parţiale distincte ale grafului dat? Două grafuri parţiale sunt distincte dacă matricele lor de adiacenţă sunt
diferite. (6p.)
010101
000010
000000
000010
000001
001000
8. Se consideră graful orientat reprezentat prin listele de adiacenţănalăturate. Câte noduri au gradul extern mai mare
decât gradul intern? (4p.)
nod lista
1: 2, 6, 5
2: 3
3: 1
4: 6
5: 6
6: 2
a. 3 b. 2 c. 1 d. 4
9, 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
10. Se consideră un graf orientat cu 6 noduri care are următoarele proprietăti:
- suma gradelor externe ale tuturor vârfurilor grafului este egală cu 6
- sunt numai 3 vârfuri care au gradul intern egal cu 1
Care este valoarea maximă pe care o poate avea gradul extern al unui vârf din graful dat?

11. Se consideră graful orientat reprezentat prin matricea de adiacenţă alăturată. Care este lungimea maximă a unui drum,
de la vârful 4 până la vârful 6, format din vârfuri distincte două câte două (lungimea unui drum este egală cu numărul de
arce care compun acel drum)?
011000
000011

1
 000000
001010
110001
101000
a. 4 b. 3 c. 1 d. 5

12. Câte grafuri neorientate, distincte, cu 5 vârfuri, se pot construi? Două grafuri se consideră
distincte dacă matricele lor de adiacenţă sunt diferite. (4p.)
a. 54 b.52 c. 210 d. 410
13. Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, este reprezentat prin matricea de adiacenţă alăturată. Care dintre
vârfurile grafului au gradul exterior un număr impar? (4p.)
011000
001101
110100
000010
010000
010010
a. 1, 3, 4, 5 b. 2, 3, 4, 5 c. 1, 4, 5, 6 d. 2, 3, 5
14. Scrieţi listele def 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. (4p.)
15. 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? (4p.)
a. 12 b. 6 c. 4 d. 3
16. Se consideră graful neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,2], [1,6], [1,7], [2,3], [2,6], [3,6], [3,4],
[4,5], [4,8], [5,6], [7,8]. Care este gradul minim al unui nod din acest graf? Care sunt nodurile care au acest grad minim?
17. 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? (4p.)
a. 12 b. 14 c. 11 d. 13
18. Î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? (4p.)
a. 5 b. 20 c. 10 d. 17
19. Î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.
20. Care dintre următoarele arce trebuie adăugat unui graf orientat cu 5 noduri şi cu matricea de adiacenţă alăturată astfel
încât în acest graf să existe cel puţin un drum între oricare două vârfuri? (4p.)
01010
00100
00000
00001
10000
a. (3 , 5) b. (4 , 1) c. (5 , 3) d. (3 , 2)
21. 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: (6p.)
a. există un vârf cu gradul intern 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
22. Se consideră graful orientat din figura alăturată. Care este numărul minim de arce ce trebuie adăugate grafului şi care
sunt aceste arce, astfel încât oricare două vârfuri din graf să fie unite prin drumuri elementare?

23. 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? (4p.)
a. 2 b. 3 c. 1 d. 4

2
24 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?(4p.)

a. 1 b. 2 c. 3 d. 4
25 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

26. Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri? (4p.)
a. 4 b. 5 c. 3 d. 2
27. 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? (6p.)
a. 0 b. 1 c. 2 d. 3

28 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? (4p.)
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)
29. Un graf orientat este reprezentat cu ajutorul listelor de adiacenţă scrise alăturat. Nodurile grafului care au gradul
exterior egal cu 2 sunt: (4p.)
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
30. Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenţă alăturate. Care dintre mulţimile
următoare de noduri are toate elementele extremităţi ale unor lanţuri elementare de lungime 2 cu cealaltă extremitate în
nodul 5? (4p.)
1: 4,5,6
2: 5
3: 4
4: 1,3
5: 1,2,6
6: 1,5
a. {1,4,6} b. {2} c. {3} d. {2,6}

3
31. 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
32. Se consideră un graf neorientat cu 7 noduri numerotate de la 1 la 7 şi muchiile
[1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numărul minim de muchii ce trebuie adăugate astfel încât graful
să devină eulerian şi care sunt aceste muchii? (6p.)
33 Se consideră un graf orientat cu 5 vârfuri reprezentat în figura alăturată.
a) Care este matricea de adiacenţă corespunzătoare grafului? (6p.)
b) Scrieţi vârfurile care au gradul intern maxim. (6p.)

34 Se consideră
un graf neorientat cu 7 noduri, numerotate de la 1 la 7 şi muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].
a) Câte cicluri elementare distincte există în graf? Două cicluri sunt distincte dacă diferă prin cel puţin o muchie. (3p.)
b) Care este lungimea maximă a unui ciclu elementar din acest graf? (3p.)
c) Care este numărul minim de muchii care trebuie eliminate astfel încât graful parţial obţinut să aibă 3 componente
conexe? (6p.)
Varianta 40
35 Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,5],[1,6], [2,6], [3,4], [3,6], [3,7], [4,6],
[6,8], [7,8]. Dacă se elimină nodul 6 şi toate muchiile incidente cu acesta câte componente conexe va avea subgraful
rezultat?
36. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenţă alăturată, au gradul un număr par?
(4p.)
01001
10110
01011
01101
10110
a. 3 b. 1 c. 2 d. 5

37. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenţă alăturată, au gradul 0? (4p.)
00011
00000
00000
10000
10000
a. 2 b. 1 c. 3 d. 0
38. Un graf neorientat este reprezentat prin matricea de adiacenţă alăturată. Câte grafuri parţiale distincte, formate doar
din noduri cu gradul egal cu 2, se pot obţine din graful dat? Două grafuri sunt distincte dacă matricele lor de adiacenţă
diferă. (4p.)
01001
10110
01011
01101
10110
a. 3 b. 1 c. 2 d. 0
39. Graful orientat G este reprezentat prin matricea de adiacenţă alăturată.Câte vârfuri din graful dat au gradul interior
egal cu gradul exterior?
(4p.)
01001
10100
00011
01001
4
 10000
a. 0 b. 1 c. 3 d. 2
40. Graful neorientat G este dat prin matricea de adiacenţă alăturată. Câte vârfuri ale grafului G au gradul 1? (4p.)
00001
00110
01011
01101
10110
a. 1 b. 2 c. 3 d. 0
41. Care dintre următoarele propoziţii este falsă pentru graful orientat G, dat prin matricea de adiacenţă alăturată? (4p.)
01100
00110
00011
11000
00010
a. există cel puţin un nod în graful G care are gradul intern egal cu cel extern
b. graful G nu are circuite
c. există cel puţin un drum între oricare două noduri ale grafului G
d. graful G are 9 arce
42. Care sunt arcele care alcătuiesc un drum elementar de lungime maximă de la nodul 1 la nodul 5 pentru graful orientat
cu şase noduri numerotate de la 1 la 6, reprezentat prin matricea de adiacenţă alăturată? (6p.)
011100
000001
010100
001001
010000
000010

43. Care dintre următoarele propoziţii NU este adevărată pentru graful orientat cu 6 vârfuri,numerotate de la 1 la 6 şi ale
cărui arce sunt: (2,1), (3,6), (4,1), (4,3), (4,5),(5,2), (6,4)? (4p.)
a. vârful numerotat cu 6 aparţine unui circuit b. vârful numerotat cu 1 are gradul extern 0
c. gradul intern al vârfului numerotat cu 4 este 1 d. graful nu are circuite
44. Care este numărul de circuite distincte ale grafului orientat dat prin matricea de adiacenţă alăturată? Două circuite
sunt distincte dacă diferă prin cel puţin un arc. (4p.)
001000
101011
000000
001000
000000
000110
a. 0 b. 1 c. 2 d. 3
45. Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de numere poate fi şirul
gradelor nodurilor grafului? (4p.)
a. 4, 2, 6, 4, 2 b. 2, 2, 1, 2, 2
c. 1, 1, 1, 1, 1 d. 4, 3, 3, 4, 4
46. 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? (4p.)
a. 2 b. 4 c. 1 d. 3

47. 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? (4p.)
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
Varianta 54
48. Se consideră graful orientat din figura alăturată. Câte dintre vârfurile grafului au gradul intern egal cu gradul extern?
(4p.)
a. 3 b. 2 c. 1 d. 4

5
49. Variabila n memorează un număr natural nenul. Care este numărul total de grafuri orientate
distincte cu n noduri? Două grafuri orientate sunt distincte dacă matricele lor de adiacenţă
sunt diferite. (4p.)
a. 4𝑛∗(𝑛−1)/2 b. 3𝑛∗(𝑛−1)/2 c. 4𝑛∗(𝑛−1) d. 2n∗(n−1)/2
50. Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri,
care nu este conex? (4p.)
a. 4 b. 15 c. 12 d. 10
51. Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri
şi 6 muchii? (4p.)
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
52. 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: (4p.)
a. 2 b. 4 c. 3 d. 5
53. Dacă G este un graf neorientat cu 8 noduri şi 2 componente conexe, atunci graful are cel
mult: (4p.)
a. 28 de muchii b. 12 muchii c. 21 de muchii d. 16 muchii
54. Care este numărul minim de muchii pe care le poate avea graful neorientat G, dacă graful din figura 1 reprezintă un
subgraf al lui G, iar graful reprezentat în figura 2 este graf parţial al lui G?(4p.)
a. 8 b. 7 c. 5 d. 6

Varianta 63
3. Câte vârfuri ale grafului din figura alăturată, au gradul interior mai mare decât gradul
exterior? (6p.)

Varianta 64
3. Se consideră un graf neorientat dat prin listele de adiacenţă alăturate. Care este numărul maxim de muchii care pot fi
eliminate din graf astfel încât graful parţial rezultat să fie conex ? (6p.)
1: 2 3
2: 1 3 4
3: 1 2 4 5
4: 2 3 5
5: 3 4

4. Într-un graf orientat G cu 6 vârfuri numerotate cu numere distincte de la 1 la 6, există arc de la vârful i la vârful j dacă şi
numai dacă i<j şi j-i>1. Care sunt vârfurile din graf ce au gradul interior mai mare decât gradul exterior? (6p.)
Varianta 65
3. Care este numărul minim de muchii care trebuie adăugate grafului alăturat pentru a deveni conex şi eulerian? ( 6p.)

6
Varianta 66
2. 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? (4p.)
a. 1 b. 2 c. 0 d. 3
Varianta 67
2. Se consideră graful orientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi arcele (1,2),
(1,6), (1,5), (2,3), (3,6), (4,1), (6,4).Care este vârful accesibil din toate celelalte vârfuri ale grafului prin intermediul unor
drumuri elementare? (4p.)
a. 4 b. 1 c. 5 d. 6
Varianta 68
2. Se consideră graful orientat cu vârfurile numerotate cu numere distincte 1,2,3, ... . Graful este reprezentat printr-o
matrice de adiacenţă A. Precizaţi care este semnificaţia sumei valorilor de pe o linie oarecare x a matricei A. (4p.)
a. reprezintă numărul arcelor care au ca extremitate iniţială vârful x
b. reprezintă numărul drumurilor care conţin vârful x
c. reprezintă numărul arcelor care au ca extremitate finală x
d. reprezintă numărul drumurilor care pornesc din vârful x
Varianta 69
2. Se consideră graful orientat dat prin matricea de adiacenţă alăturată.Care este numărul de vârfuri ale grafului care au
gradul interior (intern) egal cu gradul exterior (extern)? (4p.)
00000
10111
00010
10001
01000
a. 0 b. 3 c. 2 d. 1
Varianta 70
2. Se consideră un graf orientat dat prin matricea de adiacenţă alăturată. Câte vârfuri ale grafului au proprietatea că
diferenţa absolută a gradelor (intern şi extern) este egală cu 2? (4p.)
01101
00110
11000
01101
01010
a. 5 b. 3 c. 4 d. 2

Varianta 71
1. Câte noduri ale grafului orientat cu şase noduri numerotate de la 1 la 6 şi următoarele arce:
(1,5), (1,6), (2,1), (2,3), (3,1), (3,4), (4,3), (4,5), (5,4), (6,5) au gradul interior egal cu gradul exterior? (4p.)
a. 4 b. 6 c. 5 d. 3
Varianta 72
3. Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile: [1,4],
[1,8], [2,1], [2,3], [3,1], [4,5], [4,7], [5,7], [6,5]. Scrieţi câte componente conexe are graful dat şi care este nodul ce trebuie
eliminat astfel încât subgraful obţinut să aibă un număr maxim de componente conexe.

Varianta 73
3. Se consideră graful orientat cu 6 noduri, numerotate de la 1 la 6, şi arcele (1,2), (1,5),
(1,6), (2,3), (4,3), (4,5), (6,5). Care este numărul minim de arce ce trebuie adăugate grafului astfel încât acesta să conţină
cel puţin un circuit elementar de lungime 4? Pentru graful rezultat, daţi un exemplu de astfel de circuit. (6p.)
Varianta 74
4. Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6 şi următoarele muchii: [1,3] [1,5] [2,3] [2,4] [2,6]
[5,3] [6,4].
a) Care este numărul minim de muchii ce trebuie eliminate din acest graf, astfel încât graful
parţial obţinut să nu conţină niciun ciclu? (3p.)
b) Care este numărul minim de muchii ce trebuie eliminate din graful iniţial dat, astfel încât
graful parţial obţinut să aibă exact două componente conexe? (3p.)
Varianta 75
7
2. Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6, definit prin listele de adiacentă alăturate. Câte muchii
trebuie adăugate în acest graf astfel încât el să devină graf complet ?Un graf este complet dacă există muchie între oricare 2
noduri din graf.
1: 3 5
2: 3 4 6
3: 1 2 5
4: 2 6
5: 1 3
6: 2 4.
a. 16 b. 14 c. 6 d. 8
Varianta 76
3. Fie graful orientat cu 8 vârfuri, 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 numărul minim de arce ce trebuie adăugate astfel încât, pentru oricare două vârfuri x şi y din graf să existe cel
puţin un drum de la nodul x la nodul y? (6p.)
Varianta 77
3. Fie graful orientat cu 6 vârfuri, numerotate de la 1 la 6, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (3,5). Care este numărul
minim de arce ce trebuie adăugate pentru ca toate vârfurile să aibă gradul interior egal cu gradul exterior? (6p.)
4. Care este numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii? (6p.)
Varianta 78
3. Fie graful orientat cu 7 vârfuri, numerotate de la 1 la 7, şi arcele (1,2), (2,3), (3,1), (4,5), (5,6), (5,7), (6,7), (7,4). Care este
numărul minim de arce şi care sunt respectivele arce ce ar trebui eliminate pentru ca graful parţial obţinut să nu mai
conţină circuite? (6p.)
4. Care este numărul minim de muchii ale unui graf neorientat conex, cu 100 de noduri? (6p.)
Varianta 79
4. Fie graful neorientat cu 6 noduri, numerotate de la 1 la 6, şi muchiile [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [3,5], [4,5], [4,6],
[5,6]. Care este numărul maxim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să-şi păstreze proprietatea
de graf hamiltonian? (6p.)
Varianta 80
3. Un graf orientat are 8 arce şi fiecare nod al grafului are gradul exterior un număr nenul. Doar
două dintre noduri au gradul exterior un număr impar, restul având gradele exterioare
numere pare. Care este numărul maxim de noduri pe care le poate avea graful? (6p.)

4. Se consideră graful neorientat cu 6 noduri, numerotate cu 1, 2, 3, 4, 5, 6, şi 9 muchii dat prin listele de adiacenţă
alăturate. a) Care este cel mai scurt lanţ cu o extremitate în nodul 1 şi cealaltă
extremitate în nodul 3? (3p.)
b) Care este numărul maxim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să rămână
conex? (3p.)
1: 2,5,6
2: 1,3,4
3: 2,4,6
4: 2,3,5
5: 1,4,6
6: 1,3,5

Varianta 81
2. 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]}? (4p.)
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.
Varianta 82
1. Se consideră graful orientat cu nodurile numerotate de la 1 la 5 şi arcele (1,2), (1,5), (2,1), (2,3), (2,5), (3,4), (5,2), (5,4).
Care este lungimea maximă a unui drum de la nodul 1 la nodul 4, format doar din arce distincte? (4p.)
a. 5 b. 6 c. 4 d. 7
Varianta 83
2. Se consideră graful orientat cu nodurile numerotate de la 1 la 5 şi arcele (2,1), (5,1), (1,2), (3,2), (5,2), (4,3), (2,5), (4,5).
Care este lungimea maximă a unui drum de la nodul 4 la nodul 1, format doar din arce distincte? (4p.)
a. 6 b. 5 c. 4 d. 7
Varianta 84

8
1. Se consideră graful neorientat cu nodurile numerotate de la 1 la 6 şi având muchiile [1,2], [2,3], [2,5], [2,6], [3,4], [4,5],
[4,6], [5,6]. Câte lanţuri elementare, distincte şi de lungime 3 există de la nodul 1 la nodul 4 în graful dat? Două lanţuri sunt
distincte dacă diferă prin cel puţin o muchie. (4p.)
a. 2 b. 0 c. 4 d. 3
Varianta 85
1. Se consideră graful orientat cu vârfurile numerotate de la 1 la 7 şi arcele (1,2),
(1,7), (2,3), (3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6).
Câte vârfuri din graful dat au gradul extern impar? (4p.)
a. 4 b. 3 c. 1 d. 2
Varianta 91
1. Se consideră un graf neorientat G cu 101 noduri şi 101 muchii. Numărul maxim de vârfuri
izolate ale grafului poate fi: (4p.)
a. 0 b. 10 c. 50 d. 86
Varianta 92
1. Care din următoarele arce aparţine grafului orientat cu 4 vârfuri, având gradele din tabelul
alăturat (x,yN)? (4p.)
a. (2,3) b. (1,2) c. (1,4) d. (4,1)

Varianta 93
1. Care este numărul minim de noduri ce trebuie eliminate din grafulalăturat astfel încât subgraful obţinut să nu fie conex?
(4p.)

a. 3 b. 0 c. 2 d. 1
Varianta 94
1. Care dintre nodurile grafului neorientat cu 5 noduri, numerotate de la 1 la 5, dat prin matricea de adiacenţă alăturată,
are gradul cel mai mare? (4p.)
01100
10101
11011
00101
01110
a. 4 b. 3 c. 5 d. 2
Varianta 95
4. Se dă graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacenţă alăturată. Determinaţi un
drum de lungime maximă de la nodul 1 la nodul 5 , care să fie alcătuit din arce distincte două câte două. Scrieţi lungimea
drumului determinat precum şi arcele care îl compun (lungimea unui drum este egală cu numărul de arce care îl compun).
(6p.)
01000
00111
01010
00100
00000
Varianta 96
3. Scrieţi listele de adiacenţă pentru un graf neorientat cu 5 noduri, numerotate de la 1 la 5,
care este hamiltonian dar NU este eulerian. (6p.)
4. Se dă graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacenţă alăturată. Scrieţi arcele din
care este alcătuit un drum de la nodul 1 la nodul 5, care trece prin cel puţin patru noduri. (6p.)
01000
00111
01010
00100
00000
Varianta 97
1. Se consideră un graf neorientat 5 noduri şi 3 muchii. Care este numărul maxim de noduri
9
cu grad 1 care pot exista în graf? (6p.)
a. 2 b. 3 c. 4 d. 5
Varianta 98
1. Fie graful orientat G cu 5 vârfuri, numerotate cu 1,2,3,4,5, şi arcele (1,2), (1,3), (1,4),
(2,3), (4,2), (4,5), (5,2), (2,4). Care dintre următoarele vârfuri au gradul extern
egal cu gradul intern? (4p.)
a. 2 şi 4 b. 4 şi 5 c. 1 şi 2 d. 3 şi 4
Varianta 99
1. Considerăm un graf orientat cu 7 noduri, numerotate de la 1 la 7, şi arcele: (1,6), (2,1),
(3,1), (3,4), (3,5), (6,2), (7,3). Care este lungimea maximă a unui circuit
elementar care se poate obţine în graf prin adăugarea unui singur arc? (4p.)
a. 6 b. 4 c. 3 d. 5
3. Considerăm un graf neorientat cu 5 noduri şi 3 muchii format din două componente conexe.
Ştiind că doar patru dintre noduri au gradul 1, scrieţi matricea de adiacenţă a grafului. (6p.)
Varianta 100
1. Care este numărul minim de muchii care trebuie eliminate dintr-un graf neorientat complet
cu 100 de noduri astfel încât graful parţial obţinut să fie eulerian? (4p.)
a. 4851 b. 0 c. 100 d. 50

10