andreea popovici variantele 71

7/25/2019 Andreea Popovici Variantele 71

1/4

Andreea Popovici variantele 71-80

V71:Cte noduri ale grafului orientat cu ase noduri numerotate de la 1 la 6 iurmtoarele arce:(1,5) (1,6) (2,1) (2,3) (3,1) (3,4) (4,3) (4,5) (5,4)

(6,5) au gradulinterior egal cu gradul e!terior"a. 4 b. 6 c. 5 d. 3Raspuns este c deoarece nodurile care au gradul interior egal cugradul exterior sunt: 1,2,3,4,6;

V7#:1. $ie un ar%orele cu rdcin cu 9 nodurinumerotate de la 1 la 9& Care este vectorul 'de ta(i)al acestui ar%ore tiind c nodurile 1 2 3 4 5 6 ! au e!act cte un

descendent direct *+u,"a. (1,2,3,4,5,6,,!) b. (1,2,3,4,5,6,,!,9)c. (",1,2,3,4,5,6,,!) d. (",1,2,3,4,5,6,,!,9)Raspunsul este #arianta c;$%ariantele a si d sunt gresite deoarece un #ector de tati are atateapo&itii cate noduri sunt in arbore iar cele doua #ariante nu respectaaceasta conditie;$%arianta b este gresita deoarece po&itia a 9a din #ector ar trebui sa'e " deoarece nodul 9 este radacina arborelui;

&.e consider un graf neorientat cu ! noduri numerotate de la 1 la ! imuc/iile: 1,41,! 2,1 2,3 3,1 4,5 4, 5, 6,5& .crie(i

cte componente cone!e are graful dat i care dintre nodurile acestuiatre%uie eliminate astfel nct su%graful o%(inut s ai% un numr ma!im decomponente cone!e&

*o+ponentele conexe ale graului dat sunt: -4,5, si -1,2,3

%3

1. .e consider ar%orele cu 12 noduri numerotate de la 1 la 12 de+nit prinurmtorul vector 'de ta(i): (4 ! " 3 1" 1 ! 3 2 4 1")& Care dintrenodurile ar%orelui au e!act un descendent direct *+u,"a. 6 9 11 b. 1 2 c. 5 12 6 9 11 d. 1" 1 2

Raspunsul este c.

3. .e 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 dearce care tre%uie adugate grafului astfel nct acesta s con(in cel pu(in uncircuit elementar de lungime 4"


2/4

Pentru graful reultat da(i un e!emplu de astfel de circuit&

$+ini+ 2 +uc/ii;0xe+plu de circuit ele+entar: 1,2,3,4,1;

%4:

3. .e consider un ar%ore cu 9 noduri numerotate de la 1 la 9 i cu vectorul2de ta(i) urmtor: (! ! ! 2 6 2 9 " 2)&a) 3numera(i descenden(ii nodului 2&b) Cte noduri de tip frun are acest ar%ore"

a) descendentii nodului 2 sunt: 4,6,9,5,;b) exista 3 noduri de tip run&a : 4,5,4

4. .e consider graful neorientat cu 6 noduri numerotate de la 1 la 6 iurmtoarele muc/ii:1,3 1,5 2,3 2,4 2,6 5,3 6,4&

a)Care este numrul minim de muc/ii ce tre%uie eliminate din acest graf

astfel nct graful par(ial o%(inut s nu con(in niciun ciclu"b) Care este numrul minim de muc/ii ce tre%uie eliminate din acest grafastfel nct graful par(ial o%(inut s ai% e!act dou componente cone!e"

a) +ini+ 2 +uc/ii;%, 1 +uc/ie 2,3; re&ulta 2 co+ponente conexe -1,3,5 si

-2,4,65

%5:

2. .e numete graf complet un graf n care oricare dou noduri sunt

adiacente& .e consider graful neorientat cu 6 noduri numerotate de la 1 la6 de+nit prin listele de adiacent alturate& Cte muc/ii tre%uie adugate nacest graf astfel nct el s devin graf complet"

1: 3 52: 3 4 63: 1 2 54: 2 65: 1 36: 2 4&a. 16 b. 14 c. 6 d. !

Raspunsul este a. deoarece +atricea de adiacenta trebuie sa 'e co+pleta.stel se #or adauga inca 16 +uc/ii;

4. .e consider graful orientat cu vrfuri numerotate de la 1 la i arcele(12) (25) (32) (34) (36) (56) (5) (61)& Care este numrul minimde arce care tre%uie adugate acestui graf astfel nct pentru orice dounoduri x i din mul(imea -1,2,3,4s e!iste cel pu(in un drum de la x la" 3numera(i arcele care tre%uie adugate&


3/4

rebuie adaugata 2 arce 2,3 si 4,1

%6:

3. $ie graful orientat cu ! vrfuri numerotate de la 1 la ! i arcele (1,2)(2,3) (3,1) (4,5) (5,6) (5,) (6,) (,4) (!,)& Care este numrulminim de arce care tre%uie adugate astfel nct pentru oricare dou vrfurix i din graf s e!iste cel pu(in un drum de la nodul x la nodul "

u+arul +ini+ de arce care trebuie adaugate este 3. exe+pluarcele: 3,4, ,1, 1,!;

4. Care este vectorul de ta(i pentru ar%orele cu ! noduri numerotate de la 1la ! i muc/iile 1,5 2,3 3,6 3,! 4,6 5, 6, dac se alegeca rdcin nodul numerotat cu

6"

%:4. Care este numrul minim de noduri cu gradul 1 pentru un graf neorientatcone! cu 21 noduri i 2" muc/ii"

Raspuns: 2 noduri cu gradul 1;

%!:3. $ie graful orientat cu vrfuri numerotate de la 1 la i arcele (1,2)(2,3) (3,1) (4,5) (5,6) (5,) (6,) (,4)& Care este numrul minim dearce care ar tre%ui eliminate pentru ca graful par(ial o%(inut s nu mai

con(in circuite"

Raspuns: 3 arce +ini+;

4. Care este numrul minim de muc/ii ale unui graf neorientat cone! cu 1""de noduri"

Raspuns: n$1;1"" 1 99 +uc/ii;

%9:3. .e consider ar%orele cu 13 noduri numerotate de la 1 la 13i mul(imeamuc/iilor61,4 2,5 3,! 4, 4,9 4,11 6,3 6,1" 6,12 5,613,2 2,95& ac se alege nodul notat cu 2 drept rdcin care estevectorul deta(i pentru acest ar%ore"


4/4

4. $ie graful neorientat cu 6 noduri numerotate de la 1 la 6 i muc/iile1,2 1,31,4 2,3 2,4 3,4 3,5 4,5 4,6 5,6& Care este numrulma!im de muc/ii care pot + eliminate astfel nct graful par(ial o%(inut s-i

pstree proprietatea de graf /amiltonian"

u+arul +axi+ de +uc/ii ce pot ' eli+inate astel incat graul sara+ana un gra 7a+iltonian este 3.

%!":3. $ie graful orientat cu 9 vrfuri numerotate de la 1 la 9 i arcele (1,2)(2,3) (3,1) (4,5) (5,6) (5,) (6,) (,4) (!,) (!,9) (9,!)& Care estenumrul de vrfuri cu proprietatea c gradul interior este egal cu gradule!terior "

Raspuns: 6 noduri au gradul interior egal cu gradul exterior.

4. .e consider un graf neorientat cu 9 noduri numerotate de la 1 la 9 imuc/iile 1,2 2,3 3, 4,! 4,5 4,6 5,9 6,9 ,! 6,1,& Care este numrul minim de muc/ii care tre%uie adugate pentru cagraful s devin eulerian"

rebuie adaugat +ini+ o +uc/ie pentru ca graul sa de#ina eulerian &

andreea popovici variantele 71

Documents