EXERCITII GRILA STIVA BAC 2008 SUBIECTUL II

EXERCITII GRILA GRFURI ORIENTATE BAC 2009 SUBIECTUL II

V3 1. 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. 3V41. 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 egal cu gradul interior? a. 2

b. 3

c. 1

d. 4

V8

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

- suma gradelor externe ale tuturor varfurilor grafului este egal cu 6;

- sunt doar 3 vrfuri care au gradul intern egal cu 1.

Care este valoarea maxim pe care o poate avea gradul extern al unui vrf din graful dat?

Reprezentai prin liste de adiacen un graf care ndeplinete condiiile din enunul problemei i n care unul dintre vrfuri are acest grad extern maxim.

V9 4. Se consider graful orientat G reprezentat 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? V11 1. Se consider graful orientat reprezentat prin matricea de adiacen alturat. Care este lungimea maxim a unui drum de la vrful 4 pn la vrful 6 format din vrfuri distincte dou cte dou? a. 4

b. 3

c. 1

d. 5V20 1. 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

V21 2. 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. 17V24 1. Care dintre urmtoarele arce trebuie adugat unui graf orientat cu 5 noduri, numerotate de la 1 la 5, reprezentat prin matricea de adiacen alturat, astfel nct n acest graf s existe cel puin un drum ntre oricare dou vrfuri? a. (3 , 5) b. (4 , 1) c. (5 , 3) d. (3 , 2)

V242. 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 2

d. gradul intern al oricrui vrf este egal cu 2

V27 1. Care este numrul arcelor ce au ca extremitate iniial vrful 4, n

graful orientat cu 4 vrfuri, numerotate de la 1 la 4, reprezentat prin

matricea de adiacen alturat?

a. 3

b. 2

c. 1

d. 0

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

V37 3. Se consider un graf orientat cu 5 vrfuri reprezentat n

figura alturat.

a) Care este matricea de adiacen corespunztoare grafului? b) Scriei vrfurile care au gradul intern maxim. V44 1. Graful orientat G este reprezentat prin matricea de adiacen alturat.

Cte vrfuri din graful dat au gradul interior egal cu gradul exterior?

a. 0

b. 1

c. 3

d. 2V46

1. Care dintre urmtoarele propoziii este fals pentru graful orientat G dat

prin matricea de adiacen alturat?

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

d. graful G are 9 arceV48 3. Care sunt arcele care alctuiesc 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 alturat? V49 4. Se consider un graf orientat cu 6 vrfuri 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 distincte

dac ele difer prin cel puin un arc.

a) Care este numrul total de circuite din acest graf?

b) Care este numrul total de circuite elementare din acest graf? V50 1. Fie graful orientat din figura alturat. Care este numrul de circuite elementare distincte? Dou circuite elementare sunt distincte dac difer prin cel puin un arc. a. 0

b. 1

c. 2

d. 3V53 2. 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

V54

2. Se consider graful orientat din figura alturat. Cte dintre vrfurile grafului au gradul intern egal cu gradul extern?

3 b.2

c.1

d.4

V55

2. Variabila n memoreaz un numr natural nenul. Care este numrul total de grafuri orientate

distincte care se pot forma cu aceste noduri? Dou grafuri orientate sunt distincte daca

matricele lor de adiacen sunt diferite. a. 4n*(n-1)/2

b. 3n*(n-1)/2

c. 4n*(n-1) d. 2n*(n-1)/2

V62 3. Se consider graful orientat G cu 6 vrfuri numerotate cu numerele de la 1 la 6,definit cu ajutorul listelor de adiacen alturate. Care este numrul de circuite distincte din graful G? Dou circuite sunt distinct dac difer prin cel puin un arc.

V63 3. Care dintre vrfurile grafului orientat din figura alturat,

au gradul interior un numr par?

V64 4. ntr-un graf orientat G cu 6 vrfuri numerotate cu numere distincte de la 1 la 6, exist arc de la

vrful i la vrful j dac i numai dac i1. Care sunt vrfurile din graf ce au

gradul interior mai mare dect gradul exterior? V71

2. Se d graful orientat definit prin matricea de adiacen alturat.

Precizai cte noduri ale grafului au gradul interior egal cu gradul exterior. a. 5

b. 6

c. 3

d. 4

V76*2. 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

V783. 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 i care sunt acele arce care ar trebui eliminate pentru ca graful parial obinut s nu mai conin circuite?V792. Se consider un graf orientat cu 6 vrfuri, numerotate de la 1 la 6, cu proprietatea c exist un arc 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. 2V82 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 format din noduri distincte, de la nodul 1 la nodul 4? a. 5

b. 6

c. 4

d. 7V83 1. 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? a. 1

b. 2

c. 3

d. 4

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

V92 1. Care din urmtoarele arce aparine grafului orientat cu 4 vrfuri,

avnd gradele din tabelul alturat (x,y(N)?

a. (2,3) b. (1,2) c. (1,4) d. (4,1)V95

3. 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). V963. 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. V98

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

0 1 1 0 0 0

0 0 0 0 1 1

0 0 0 0 0 0

0 0 1 0 1 0

1 1 0 0 0 1

1 0 1 0 0 0

0 1 0 1 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 1

1 0 0 0 0

0 1 0 1

0 0 0 0

0 1 0 0

1 1 1 0

1:(5,6);

2:(1,5);

3:(1,5);

4:(1,2);

5:(2);

6:(2, 4, 5);

0 1 0 0 1

1 0 1 0 0

0 0 0 1 1

0 1 0 0 1

1 0 0 0 0

0 1 1 0 0

0 0 1 1 0

0 0 0 1 1

1 1 0 0 0

0 0 0 1 0

0 1 1 1 0 0

0 0 0 0 0 1

0 1 0 1 0 0

0 0 1 0 0 1

0 1 0 0 0 0

0 0 0 0 1 0

1: 2 6

2: 3

3:

4: 3

5: 4 6

6: 3

0 1 0 1 0 0

1 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

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

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