Grile Grafuri Orientate

8/6/2019 Grile Grafuri Orientate

http://slidepdf.com/reader/full/grile-grafuri-orientate 1/8

GRILE ORIENTATE

1.

2. Se d graful orientat definit prin matricea de adiacen alturat. Precizai câte noduri alegrafului au gradul interior egal cu gradul exterior.0 1 0 1 0 01 0 1 0 0 01 1 0 0 0 10 0 0 0 1 00 0 1 0 0 1

0 0 0 0 1 0a. 5 b. 6 c. 3 d. 4

3. Se consider graful orientat dat prin matricea de adiacen alturat. Care este numrulde vârfuri ale grafului care au gradul interior (intern) egal cu gradul exterior (extern)?0 0 0 0 01 0 1 1 10 0 0 1 01 0 0 0 10 1 0 0 0

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

4. Se consider un graf orientat dat prin matricea de adiacen alturat. Câte vârfuri alegrafului au proprietatea c diferena absolut a gradelor (intern i extern) este egal cu 2?0 1 1 0 10 0 1 1 01 1 0 0 00 1 1 0 10 1 0 1 0

a. 5 b. 3 c. 4 d. 2

5. Câte noduri ale grafului orientat cu ase noduri numerotate de la 1 la 6 i urmtoarele

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 gradulexterior?a. 4 b. 6 c. 5 d. 3

6.



14. Fie graful orientat cu 8 vârfuri, 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 încât, pentruoricare dou vârfuri x i din graf s existe cel puin un drum de la nodul x la nodul este:a. 2 b. 4 c. 0 d. 1

15.

16.

17.

18.

19. Fie graful orie9

@

at 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 urmtoarele vârfuri au gradul eA tern egal cu gradul intern? (4p.)

a. 2 i 4 b. 4 i 5 c. 1 i 2 d. 3 i 4



20. Considerm 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 obine în

graf prin adugarea unui singur arc? (4p.)

a. 6 b. 4 c. 3 d. 5

21.. Un graf orientat este reprezentat cu ajutorul listelor de adiacen scrise alturat. Nodurilegrafului care au gradulexterior egal cu 2 sunt: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

22. Un graf orientat este memorat cu ajutorul listelor alturate de adiacen. Sumaelementelor de pe ultima linie a matricei de adiacen asociat grafului este egal cu:1:(5,6); 4:(1,2);

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

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

22.

23.

24.



25.

26.

27.

28. Se consider graful orientat G repre B entat prin listele de adiacen alturate. Care este

lungimea maxim a unui drum elementar din acest graf? Care sunt arcele care compun un drum cu

aceste proprieti?

29. Se consider graful orientat repre B entat prin matricea de adiacen alturat. 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 numrul de arce care compun acel drum ) ?



30. Se consider un graf orientat cu 6 noduri care are urmtoarele proprietti:

- suma gradelorexterne 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?

31. Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, este repreC

entat prin matricea de adiacen alturat. Care dintre vârfurile grafului au gradul exterior un numr impar?

32. Graful orientat G este reprezentat prin matricea de adiacen alturat.Câte vârfuri din graful dat au gradul interior egal cu gradul exterior?

0 1 0 0 11 0 1 0 00 0 0 1 10 1 0 0 11 0 0 0 0a. 0 b. 1 c. 3 d. 2

33. Se considergrafulorientat cu vârfurilenumerotate de la 1 la 7 iarcele(1,2),(1,7),(2,3),

(3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6).Câtevârfuri din grafuldat au gradul extern impar?(4 .)a. 4 b. 3 c. 1 d. 2

34. Se consider un graf orientat cu 6 vârfuri numerotate de la 1 la 6, ale crui arce sunt:(2,1), (3,6), (4,1), (4,3), (4,5), (5,2), (6,4), (1,4). Dou circuite sunt distinctedac ele difer prin cel puin un arc. Într-un circuit arcele sunt distincte.a) Care este numrul total de circuite din acest graf? (3 .)b) Care este numrul total de circuite elementare din acest graf? (3 .)

35. Fie graful orientat din figura alturat. Care este numrul decircuite elementare distincte? Dou c ircuite elementare suntdistincte dac difer prin cel puin un arc. (4 .)

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

36. Care dintre urmtoarele propoziiiNU este adevrat pentru graful orientat cu 6 vârfuri,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)? (4 .)a. vârful numerotat cu 6 aparine 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

37. Care este numrul de circuite distincte ale grafului orientat dat prin matricea de adiacenalturat? Dou circuite sunt distincte dac difer prin cel puin un arc. (4 .)



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

38. 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 numrul minim de arce ce trebuie adugate pentru catoate vârfurile s aib gradul interior egal cu gradul exterior? (6 .)

39. .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 numrul minim de arce i care suntrespectivele arce ce ar trebui eliminate pentru ca graful parial obinut s nu mai conincircuite? (6 .)

40. Un graf orientat are 8 arce i fiecare nod al grafului are gradul exterior un numr nenul.Doar dou dintre noduri au gradul exterior un numr impar, restul având gradele exterioare

numere pare. Care este numrul maxim de noduri pe care le poate avea graful? (6 .)

41. Fie graful orientat cu 9 vârfuri 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 sunt vârfurile cuproprietatea c gradul interior este egal cu gradul exterior ? (6 .)

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

43. 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 pare?(4 .)

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

44. 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 1la nodul 4, format doar din arce distincte? (4 .)a. 5 b. 6 c. 4 d. 7

45. 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 drumde la nodul 4 la nodul 1, format doar din arce distincte? (4 .)a. 6 b. 5 c. 4 d. 7

46. Se consider graful orientat G, cu 6 vârfuri numerotate cu numerelede la 1 la 6, definit cu

ajutorul listelor de adiacen alturate. Construii matricea de adiacen corespunztoare grafului

orientat G1, cu 6 vârfuri, în care exist arc între vârfurile distincte i i j dac i numai dac în graful G

exist cel puin un drum de la i la j.



1: 2 6

2: 3

3:

4: 3

5: 4 6

6: 3

47. Într-un graf orientat G cu 6 vârfuri numerotate cu numeredistincte 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?

48. Se consider graful orientat definit prin mulimea 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?

a. 4 b. 1 c. 5 d. 6

49. Se consider graful orientat cu vârfurile numerotate cu numere distincte 1,2,3, ... . Grafuleste reprezentat printr-o matrice de adiacen A. Precizai care este semnificaia sumei valorilor de

pe o linie oarecare x a matricei A.

a. reprezint numrul arcelor care au caextremitate iniial vârful x

b. reprezint numrul drumurilor care conin vârful x

c. reprezint numrul arcelor care au ca extremitate final x

d. reprezint numrul drumurilor carepornesc din vârful x

50.

Grile Grafuri Orientate

Documents

Transcript of Grile Grafuri Orientate