Fisa aplicativa Grafuri orientate1. Se consider un graf orientat cu 6 noduri numerotate de la 1 la 6 i cu mulimea arcelor format doar din arcele:

- de la fiecare nod numerotat cu un numr neprim i (i>1) la toate nodurile numerotate cu numere ce aparin mulimii divizorilor proprii ai lui i (divizori diferii de 1 i de i)

- de la nodul numerotat cu 1 la nodul numerotat cu 6

- de la fiecare nod numerotat cu un numr prim i la nodul numerotat cu i-1

Pentru graful dat, cte dintre nodurile grafului au gradul exterior strict mai mare dect gradul interior? a. 1 b. 2 c. 4 d. 3

2. Fie graful orientat G cu 5 vrfuri, 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 urmtoarele vrfuri au gradul extern egal cu gradul intern? a. 2 i 4 b. 4 i 5 c. 1 i 2 d. 3 i 43. Se d graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacen alturat. Scriei arcele din care este alctuit un drum de la nodul 1 la nodul 5, care trece prin toate nodurile grafului. 0 1 0 0 0

0 0 1 1 1

0 1 0 1 0

0 0 1 0 0

0 0 0 0 0

4. Se d graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacen alturat. Determinai un drum de lungime maxim de la nodul 1 la nodul 5 , care s fie alctuit din arce distincte dou cte dou. Scriei lungimea drumului determinat precum i arcele care l compun (lungimea unui drum este egal cu numrul de arce care l compun). (6p.)0 1 0 0 0

0 0 1 1 1

0 1 0 1 0

0 0 1 0 0

0 0 0 0 0

5. Care dintre urmtoarele arce aparine grafuluiorientat cu 4 vrfuri, avnd gradele din tabelulalturat ?a. (2,3) b. (1,2) c. (1,4) d. (4,1)

6. Se consider graful orientat cu vrfurile 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). Cte noduri cu gradul extern par exist n graful dat? a. 3 b. 2 c. 4 d. 07. Se consider graful orientat cu nodurile numerotate de la 1 la 5 i arcele (1,2), (1,4),(2,1), (2,5), (3,2), (4,3), (5,1), (5,4). Care este numrul minim de arce care poate fi adugat pentru ca toate nodurile s aib i gradul extern i gradul intern numere par? a. 2 b. 1 c. 0 d. 3

8. 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 format din noduri distincte, de la nodul 1 la nodul 4? a. 5 b. 6 c. 4 d. 7

9. Fie graful orientat cu 9 vrfuri numerotate de la 1 la 9 i arcele (1,2) (2,3) (3,1) (4,5) (5,6) (5,7) (6,7) (7,4) (8,7) (8,9) (9,8). Care este numrul de vrfuri cu proprietatea c gradul interior este egal cu gradul exterior ?10. Se consider un graf orientat cu 6 vrfuri, numerotate de la 1 la 6, cu proprietatea c exist o muchie cu extremitea iniial n vrful i i extremitea final n vrful j dac i este divizor al lui j. Gradul interior (intern) maxim al vrfurilor din acest graf este:a. 3 b. 5 c. 4 d. 2

11. Fie graful orientat cu 7 vrfuri 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 numrul minim de arce care ar trebui eliminate pentru ca graful s nu mai conin circuite?

12. Fie graful orientat cu 8 vrfuri, numerotate de la 1 la 8, i arcele (1,2), (2,3), (3,1), (4,5), (6,5), (5,7), (7,6), (7,4), (8,7). Numrul minim de arce care trebuie adugate astfel nct, pentru oricare dou vrfuri x i y din graf s existe cel puin un drum de la nodul x la nodul y este: a. 2 b. 4 c. 0 d. 1

13. Se consider graful orientat cu 7 vrfuri, numerotate de la 1 la 7, i arcele (1,2), (2,5), (3,2), (3,4), (3,6), (5,6), (5,7), (6,1). Care este numrul minim de arce care trebuie adugate acestui graf astfel nct, pentru orice dou noduri x i y, din mulimea {1,2,3,4} s existe cel puin un drum de la x la y? Enumerai arcele care trebuie adugate.

14. 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 numrul minim de arce care trebuie adugate grafului astfel nct acesta s conin cel puin un circuit elementar de lungime 4? Pentru graful rezultat, dai un exemplu de astfel de circuit.

15. Se consider graful orientat cu 5 noduri, numerotate de la 1 la 5, definit prin matricea de adiacen alturat. Indicai numrul minim de arce care trebuie adugate grafului astfel nct, pentru orice dou noduri x i y ale sale, s existe cel puin un drum de la x la y.

0 1 0 0 00 0 1 1 1

0 1 0 1 0

0 0 1 0 0

0 0 0 0 016. Se d graful orientat definit prin matricea de adiacen alturat. Precizai cte noduri ale grafului au gradul interior egal cu gradul exterior. 0 1 0 1 0 01 0 1 0 0 0

1 1 0 0 0 1

0 0 0 0 1 0

0 0 1 0 0 1

0 0 0 0 1 0

a. 5 b. 6 c. 3 d. 417. ntr-un graf orientat G cu 6 vrfuri, numerotate cu numere distincte de la 1 la 6, exist arc de la i la j dac i numai dac i1. Cte vrfuri din graf au gradul interior mai mare dect gradul exterior?

18. Care dintre vrfurile grafului orientat din figura alturat, au gradul interior un numr par?19. Se consider graful orientat G cu 6 vrfuri definit cu ajutorul listelor de adiacen alturate. Care este numrul de circuite distincte din graful G? Dou circuite sunt distincte dac difer prin cel puin un arc.

1: 2 62: 3

3:

4: 3

5: 4 6

6: 320. Se consider graful orientat din figura alturat. Cte dintre vrfurile

grafului au gradul intern egal cu gradul extern?

a. 3 b. 2 c. 1 d. 421. Se consider un graf orientat cu 5 vrfuri i 8 arce. Care dintre urmtoarele iruri de numere pot fi gradele exterioare ale vrfurilor 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

22. Fie graful orientat din figura alturat. Care este numrul de circuite elementare distincte? Un circuit este elementar dac acesta conine doar vrfuri distincte, excepie fcnd primul carecoincide cu ultimul. Dou circuite elementare

sunt distincte dac difer prin cel puin un arc. a. 0 b. 1 c. 2 d. 3

23. Care este numrul de circuite ale unui graf orientat cu 6 vrfuri numerotate de la 1 la 6, i ale crui arce sunt: (2,1),(3,6),(4,1),(4,3),(4,5),(5,2), (6,4). Dou circuite sunt distincte dac difer prin cel puin un arc.

24. Care este lungimea celui mai scurt drum de la nodul 1 la nodul 5

pentru graful orientat din figura alturat?

25. Care dintre urmtoarele propoziii este fals pentru graful orientat G dat prin matricea de adiacen alturat? 0 1 1 0 00 0 1 1 0

0 0 0 1 1

1 1 0 0 0

0 0 0 1 0

a. exist cel puin un nod n graful G care are gradul intern egal cu cel extern

b. graful G nu are circuite

c. exist cel puin un drum ntre oricare dou noduri ale grafului G

26. Se consider un graf orientat cu 5 vrfuri reprezentat n figura alturat. a) Care este matricea de adiacen corespunztoare grafului? b) Scriei care este gradul intern al vrfului 5 i gradul extern al vrfului 1.27. Un graf orientat este memorat cu ajutorul listelor alturate de adiacen. Suma elementelor de pe ultima linie a matricei de adiacen asociat grafului este egal cu: a. 3 b. 0 c. 1 d. 51:(5,6); 4:(1,2);

2:(1,5); 5:(2);

3:(1,5); 6:(2, 4, 5);

28. Care din urmtoarele proprieti este adevrat pentru un graf orientat cu n vrfuri i n arce (n>3) care are un circuit de lungime n: a. exist un vrf cu gradul intern n-1 b. pentru orice vrf gradul intern i gradul extern sunt egale

c. graful nu are drumuri de lungime strict mai mare dect 2d. gradul intern al oricrui vrf este egal cu 229. 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? a. 5 b. 20 c. 10 d. 1730. Suma gradelor interne ale tuturor vrfurilor unui graf orientat este ntotdeauna egal cu:a. numrul valorilor de 1 aflate sub diagonala principal n matricea sa de adiacen

b. produsul gradelor externe ale tuturor vrfurilor grafului

c. suma tuturor valorilor aflate deasupra diagonalei principale n matricea sa de adiacen

d. suma gradelor externe ale tuturor vrfurilor grafului