Date post: | 31-Oct-2015 |
Category: |
Documents |
Upload: | maria-todircan |
View: | 259 times |
Download: | 1 times |
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
7/16/2019 Exerciţii-GRAFURI
http://slidepdf.com/reader/full/exercitii-grafuri 2/3
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
7/16/2019 Exerciţii-GRAFURI
http://slidepdf.com/reader/full/exercitii-grafuri 3/3
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.