Grafuri – aplicatii

1.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

2. Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelorformată doar din arcele:

- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cunumere 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-1Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte? (4p.)a. 6 b. 5 c. 3 d. 4

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 cunumere 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

4. 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? Doua grafuri partiale sunt distincte daca matricele lor de adiacenţă sunt diferite. (6p.)

0 1 0 1 0 10 0 0 0 1 00 0 0 0 0 00 0 0 0 1 00 0 0 0 0 10 0 1 0 0 0

5. Se consideră graful orientat reprezentat prin listele de adiacenţă alăturate. Câte noduri au gradul extern mai mare decât gradul intern? (4p.)a. 3 b. 2 c. 1 d. 4

6. 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 1Care este valoarea maximă pe care o poate avea gradul extern al unui vârf din graful dat?(6p.)

7. Un graf orientat este reprezentat prin matricea de adiacenţă dată alăturat. Care sunt nodurile pentru care gradul interior este mai mare decât gradul exterior? (4p.)0 1 1 0 0 00 0 1 1 0 11 1 0 1 0 00 0 0 0 1 00 1 0 0 0 00 1 0 0 1 0

a. 2, 4, 5, 6 b. 2, 4, 5 c. 1, 4, 5 d. 1, 3, 68. Î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

9. 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 egalec. graful nu are drumuri de lungime strict mai mare decât 2d. gradul intern al oricărui vârf este egal cu 2

10. 11.

12.

13.

14. 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 0c. gradul intern al vârfului numerotat cu 4 este 1 d. graful nu are circuite

15. 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.

0 0 1 0 0 01 0 1 0 1 10 0 0 0 0 00 0 1 0 0 00 0 0 0 0 00 0 0 1 1 0

a. 0 b. 1 c. 2 d. 3