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 : (4p.)
a. arbore b. graf eulerian
c. graf neconex d. graf aciclic (graf care nu conţine niciun
ciclu)
Raspuns: b. Graful fiind complet.
2. 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? (4p.)
- 15 b. 1 c. 6 d. 21
Raspuns: a.15 – un graf neorientat complet are n(n-1)/2=21 muchii, iar un arbore trebuie sa aiba (n-1)=6 muchii. => 21-6=15
3. 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
Raspuns: a.
Numarul de noduri trebuie sa fie divizibil cu 3 => singura posibiliatete este 12
4. Î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
Raspuns: c.10, deoarece suma gradelor interne este egala cu suma gradelor externe.
5. 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 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
6. 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? (6p.)
- x=1 b. x<3 c. x>3 d. nicio valoare
Raspuns: d. suma gradelor este 15+x. => numarul de muchii = (15+x)/2
Intr-un arbore numarul de muchii este n-1=7.Iar (15+x)/2>7pentru orice x.>0.
