exerciţii-grafuri

7/16/2019 Exerciţii-GRAFURI

http://slidepdf.com/reader/full/exercitii-grafuri 1/3

Exerciţii – Grafuri şi arbori GRAFURI NEORIENTATE

1.Se consideră graful neorientat din desenul alăturat.

1.1.Mulţimea nodurilor grafului este:a)X={1,2,3,4,5,6,7,8,9}; b)X={5,6,7,8}; c)X={1,3,9};d)X={1,2,3,4,9}.

1.2.Nodurile incidente cu muchia [6,8] sunt:a)6; b)8; c)6,8; d)5,6,7,8.1.3.Numărul nodurilor terminale ale grafului din desen

este:a)9; b)8; c)5; d)2.

1.4.Şirul de noduri 5,8,6,7,8 este pentru graful dindesen:a)un lanţ elementar ; b)un ciclu; c)un lanţ

neelementar; d)un ciclu elementar.1.5.Nodurile cu gradul impar din graf sunt:

a)2,4,6; b)1,3,5; c)2,4,6,8; d)1,3,5,7,9.1.6.Numărul de componente conexe ale grafului din desen este :a)2; b)1; c)3; d)9.

1.7.Numărul minim de muchii ce trebuie eliminate astfel încât graful din desen să aibă 5componente conexe este:a)2; b)1; c)3; d)4.

1.8.Lungimea maximă a unui lanţ elementar de la nodul 5 la 7 este:a)3; b)1; c)7; d)2.

1.9.Lista de adiacenţă a nodului 3 este:

a)1,2,4,5,6,7,8; b)1; c)1,3,9; d)1,9.2.Fie graful neorientat cu nodurile {1,2,3,4,5,6} şi cu proprietatea că există muchie între

nodurile i şi j, dacă i divide j sau j divide i(i≠j). 2.1.Care este nodul de grad maxim?

a)6; b)1; c)2; d)5.2.2Câte muchii are graful?a)8; b)6; c)5; d)0.

2.3.Care este lungimea celui mai mare ciclu elementar al grafului?a)0; b)1; c)2; d)5.

2.4.Care este matricea de adiacenţă a grafului?a) b) c)

d)

4

2

3

9

1

5

68

7



3. Se consideră graful din figura alăturată.

3.1.Câte noduri izolate are graful?a)2; b)3; c)1; d)0.3.2.Nodurile cu grad impar sunt:

a)1,3,4,6 b)1,3 c)1,4,6 d)2,5.3.3.Care este matricea e adiacenţă a grafului?

a) b) c)

d)

3.4.Lista de adiacenţă a nodului 3 este:

a)1,2,3,4,5,6 b)1,2,5 c)1,2,3,5 d)4,6.3.5.Numărul de muchii ce trebuie adăugate pentru ca graful să devină complet este:a)2 b)1 c)5 d)10.

3.6.Cel mai lung lanţ elementar din graf este :a)1,3,2,5 b)1,3,2,5,4,6 c)4,5,1,2,3 d)5,2,3.

3.7.Pentru a transforma graful din enunţ într -un arbore cu 6 noduri este suficient să :a)adăugăm o muchie şi să eliminăm două muchii;b)eliminăm muchia [2,5] şi să adăugăm muchia [4,5];

c)eliminăm una din componente conexe;d)unim prin muchii noi, componentele conexe.

3.8.Numărul de grafuri neorientate care se pot forma cu aceste noduri este:a)220 b)38 c)215 d)314 3.9.Numărul minim de muchii ce trebuie eliminate pentru a obţine 4 componente conexe

este:a)1 b)3 c)2 d)4.

4.Se consider ă un graf neorientat cu vârfurile numerotate 1,2,3,…..,13 şi muchiile:[1,11], [2,7], [2,8], [3,5], [5,12], [6,7], [7,8], [8,6], [8,10], [8,4], [9,5], [10,4].

4.1.Câte noduri ale grafului din enunţ au gradul maxim?a)1 b)2 c)5 d)3.

4.2.Câte noduri izolate are graful din enunţ?a)1 b)2 c)0 d)3.4.3.Câte noduri terminale are graful din enunţ ?

a)1 b)2 c)0 d)5.

4.4.Care sunt nodurile adiacente cu nodul 7 în graful din enunţ ?a)1,11 b)2,6,8 c)6,8,10 d)8.

001000

000110

100000

010011

010100

000100

000110

100000

001000

010011

010100

000100

001000

010011

010100

000100

000110

100000

0000

0011

0100

0100

1

4

6

3

52



4.5.Câte muchii sunt incidente cu muchia [7,8] în graful din enunţ ?a)3 b)12 c)6 d)4.

4.6.Câte lanţuri de la nodul 1 la nodul 3 există în graful din enunţ ?a)1 b)2 c)0 d)3.4.7.Câte lanţuri elementare distincte cu 6 noduri există în graf ?

a)1 b)2 c)0 d)3.4.8.Câte elemente de 1 are linia 13 din matricea de adiacenţă a grafului?

a)1 b)2 c)12 d)0.

4.9.Câte cicluri elementare distincte de lungime 3 există în graf ?a)1 b)2 c)0 d)3.

4.10.Câte componente conexe are graful?a)1 b)2 c)4 d)3.

4.11.Care este numărul minim de muchii ce trebuie adăugate astfel încât să obţinem ungraf conex?a)1 b)2 c)4 d)3.

4.12.Care este numărul minim de muchii ce trebuie adăugate astfel încât să obţinem unarbore?

a)1 b)2 c)4 d)nu se poate obţine

5.Se consideră un arbore cu 16 noduri numerotate cu 1,2,…..,16. Tabelul de mai josconţine listele descendenţilor direcţi ai fiecărui nod al arborelui:

1: 2: 3: 2, 10, 12

4: 6

5: 6: 7: 13

8:

9: 10: 4, 1611: 1, 8

12:

13: 9, 1114: 15: 3, 7

16: 5, 14

5.1.Care este rădăcina arborelui dat?a)2 b)4 c)5 d)15.

5.2.Care este vectorul tată al arborelui dat?a)T=(6,6,16,7,0,14,8,5,5,11,7,9,9,9,11,14)b)T=(11,3,15,10,16,4,15,11,13,3,13,3,7,16,0,10)

c)T=(11,3,15,16,16,4,15,11,13,3,6,3,7,16,0,10)d)T=(11,3,15,10,16,4,4,11,13,3,4,3,7,16,0,10).5.3.Câte lanţuri de lungime 3 care pleacă din rădăcină există în arbore?

a)2 b)4 c)5 d)3.5.4.Câte nivele are arborele?

a)6 b)4 c)5 d)3.5.5.Care este înălţimea arborelui?a)6 b)4 c)5 d)3.

5.6.Câte muchii are arborele?a)15 b)30 c)14 d)16.

5.7.Câte frunze are arborele?a)6 b)4 c)8 d)5.5.8.Care este lungimea celui mai lung lanţ elementar de la nodul 1 la nodul 5?a)6 b)4 c)5 d)8.5.9.Care sunt nodurile cu grad maxim din arbore?

a)13,15,3,10 b)15 c)3 d)11,16.

exerciţii-grafuri

Documents