Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

 
CATEGORII DOCUMENTE


AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

Grafuri neorientate - Teste grila

calculatoare


loading...



DOCUMENTE SIMILARE

Trimite pe Messenger
URL
Gestiunea unui Hipermarket
CONTROLERE LOGICE PROGRAMABILE
CAIET DE PRACTICA INFORMATICA
Administrarea datelor Undo Oracle9I
Semnale
Curs Internet
Arhitectura Hardware
Editorul de prezentari Microsoft PowerPoint
Clasificarea datelor - Biostatistica

TERMENI importanti pentru acest document

: teste grila grafuri neorientate : grile grafuri neorientate : teste grila grafuri : grafuri neorientatE :

Grafuri

Grafuri neorientate - Teste grila

1.               

V_88_I_5. Care este numarul minim de noduri pe care il poate contine un graf neorientat cu 50 de muchii, si in care 15 noduri sunt izolate?

a.

25

b.

66

c.

65

d.

26

2.               

V_1_I_6. Se considera un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 si muchiile: [1,3], [1,7], [2,6], [3,7], [5,2], [5,6], [8,4]. Cate componente conexe are graful?

a.

2

b.

3

c.

8

d.

1

3.               

V_2_I_3. Se considera un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 si muchiile: [1,3], [1,7], [2,6], [3,7], [5,2], [5,6], [8,4]. Care este numarul minim de muchii ce pot fi adaugate astfel incat graful sa devina conex?

a.

0

b. 2

c. 3

d. 4

4.               

V_56_I_5. Care este numarul maxim de varfuri izolate pe care le poate avea un graf neorientat cu 8 noduri si 12 muchii?

a.

0

b.

2

c.

3

d.

1

5.               

V_27_I_2. Se considera graful neorientat din figura alaturata.

Numarul maxim de muchii ce pot fi eliminate din graf astfel incat in graful partial rezultat sa fie conex este:

a.

0

b.

1

c.

2

d.

3

6.               

V_29_I_5. Se considera graful neorientat din figura alaturata.

Numarul maxim de muchii ce pot fi eliminate din graf astfel incat graful partial rezultat sa fie conex este:

a.

4

b.

5

c.

3

d.

2

7.               

V_65_I_4. Intr-un graf neorientat G, notam cu n numarul de varfuri si cu m numarul de muchii. Daca graful este un arbore atunci intre n si m exista urmatoarea relatie matematica:

a.

m=n+2

b.

n=m-1

c.

n=m+1

d.

n=m+2

8.               

V_24_I_2.Care este numarul minim de muchii care trebuie eliminate astfel incat graful neorientat din figura alaturata sa aiba doua componente conexe?

a.

5

b.

2

c.

3

d.

4

9.               

V_95_I_8.Se considera graful neorientat cu 6 noduri si 9 muchii dat prin listele de adiacenta alaturate. Care este numarul maxim de muchii care se pot elimina astfel incat graful sa ramana conex?

1: 2 5 6

2: 1 3 4

3: 2 4 6

4: 2 3 5

5: 1 4 6

6: 1 3 5

a.

3

b.

6

c.

5

d.

4

 

10.           

V_57_I_4.Daca G este un graf neorientat cu n varfuri si n-2 muchii, atunci graful :

a.

este conex

b.

este arbore

c.

este acicilic daca si numai daca are 2 componente conexe

d.

nu poate avea varfuri izolate

11.           

V_64_I_3. Fie graful neorientat G(X,V), cu X= si V=. Stabiliti care dintre propozitiile urmatoare este adevarata:

a.

Numarul varfurilor de grad par este egal cu numarul varfurilor de grad impar.

b.

Matricea de adiacenta asociata grafului G nu este simetrica fata de diagonala secundara.

c.

Cel mai scurt lant de la varful 1 la varful 4 are lungimea 3

d.

Subgraful generat de varfurile nu este conex.

12.           

V_74_I_7. Determinati cate componente conexe are graful neorientat, a carui matrice de adiacenta este data alaturat:

0 1 0 0 0 1 1

1 0 0 0 0 1 1

0 0 0 1 0 0 0

0 0 1 0 0 0 0

0 0 0 0 0 0 0

1 1 0 0 0 0 1

1 1 0 0 0 1 0

a.

1

b.

4

c.

3

d.

2

13.           

V_66_I_3.Numarul maxim de componente conexe ale unui graf neorientat cu 5 noduri si 4 muchii este:

a.

4

b.

2

c.

3

d.

1

14.           

V_91_I_6.Liniile si coloanele matricei de adiacenta asociata grafului alaturat sunt numerotate cu 1, 2, , 6, corespunzator nodurilor grafului. Care dintre urmatoarele variante este una din liniile matricei de adiacenta?

a.

0 0 1 1 0 1

b.

0 0 0 0 1 0

c.

0 1 1 1 0 0

d.

1 1 1 0 1 1

15.           

V_78_1_5. Pentru un graf neorientat cu 15 noduri si 14 muchii, numarul maxim de noduri terminale este:

a.

14

b.

7

c.

2

d.

10

16.           

V_79_I_6.Pentru graful neorientat conex cu 7 noduri, in care toate nodurile au acelasi grad, care dintre urmatoarele variante nu poate fi gradul unui nod?

a.

3

b.

2

c.

4

d.

6

17.           

V_80_I_4. Se considera graful neorientat cu 13 noduri si multimea muchiilor . Identificati care sunt nodurile care formeaza componenta conexa cu numar maxim de noduri terminale:

a.

3,6,8,10,12

b.

2,5,3,6,8,10,12

c.

1,4,7,9,11

d.

2,5

18.           

V_70_I_1.Se considera graful neorientat G=(X,U) unde X= si U=.

Stabiliti care este numarul maxim de muchii care pot fi eliminate pentru a se obtine un graf partial care sa fie conex a lui G.

a.

3

b.

0

c.

2

d.

1

19.           

V_67_I_7.Identificati care din secventele urmatoare reprezinta sirul gradelor nodurilor unui graf complet.

a.

1 2 3 4

b.

1 2 12 12

c.

5 5 5 5 5

d.

4 4 4 4 4

20.           

V_3_I_7. Se considera un graf neorientat dat prin matricea de adiacenta alaturata. Cate cicluri elementare distincte si de lungime 3 exista in graful din enunt? (Doua cicluri elementare sunt distincte daca difera prin cel putin o muchie).

0 0 1 0 0 0 0 0

0 0 0 1 1 1 1 1

1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 1

0 1 0 0 0 0 1 0

0 1 0 0 0 0 0 1

0 1 0 0 1 0 0 0

0 1 0 1 0 1 0 0

a.

4

b.

0

c.

2

d.

3

21.           

V_5_I_8. Se considera un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 si muchiile [1,2], [1,5], [2,8], [3,7], [4,5], [5,7], [6,4], [7,6], [8,3], [8,7]. Care este numarul minim de muchii ce pot fi eliminate astfel incat graful obtinut sa aiba trei componente conexe?

a.

3

b.

4

c.

2

d.

5

22.           

V_81_I_2. Un graf neorientat si conex are n noduri si n-1 muchii. Care este numarul minim de muchii ce trebuie adaugate astfel incat sa se obtina un ciclu?

a.

b.

c.

0

d.

1

23.           

V_87_I_7. Pentru graful neorientat G=(X,U) unde X= si U= care este numarul minim de muchii care se elimina pentru a obtine un graf cu trei componente conexe?

a.

1

b.

3

c.

2

d.

4

24.           

V_82_I.1. Se considera graful neorientat din figura alaturata. Care dintre succesiunile urmatoare de noduri reprezinta un lant elementar de la nodul 1 la nodul 5?

a.

1, 6, 2, 3, 6, 5

c.

1, 3, 6, 5

b.

1, 2, 6, 3, 5

d.

1, 5

25.           

V_84_I_4. Se considera graful neorientat dat prin lista de muchii: (1,2), (1,3), (3,4), (3,5), (3,6), (4,8), (4,7). Care este numarul minim de muchii ce trebuie eliminate din graf astfel incat acesta sa nu mai fie conex?

a.

3

b.

nicio muchie

c.

2

d.

1

26.           

V_85_I_1. Un graf neorientat cu 9 noduri are 2 componente conexe. Stiind ca in graf nu exista noduri izolate, care este numarul maxim de muchii din graf?

a.

22

b.

29

c.

18

d.

16

27.           

V_93_I.1. Pentru graful neorientat reprezentat in figura alaturata determinati numarul minim de muchii care pot fi eliminate astfel incat graful ramas sa nu contina noduri izolate si sa fie neconex.

a.

4

b.

5

c.

2

d.

3

28.           

V_90_I_8. Fie un graf neorientat cu n=30 noduri si m=15 muchii. Numarul componentelor conexe pe care le poate avea acest graf este:

a.

cel putin 1 si cel mult 30

b.

cel putin 10 si cel mult 15

c.

exact 15

d.

cel putin 15 si cel mult 25

29.           

V_49_I_3. Graful neorientat este dat prin matricea de adiacenta alaturata. Stabiliti care dintre urmatoarele afirmatii este adevarata:

0 1 1 0 0

1 0 1 0 0

1 1 0 0 0

0 0 0 0 1

0 0 0 1 0

a.

nodurile 2, 3, 4 formeaza un ciclu hamiltonian

b.

nodul 5 are gradul 0

c.

nodul 1 este legat printr-un lant de nodul 4

d.

nodurile 4 si 5 apartin aceleiasi componente conexe

30.           

V_50_I_3. Un graf neorientat cu n varfuri care are proprietatea ca oricare doua noduri diferite sunt adiacente are un numar de muchii egal cu:

a.

n*(n-1)/2

b.

n*n/2

c.

n*(n+1)/2

d.

n*n

31.           

V_20_I_2. Intr-un graf neorientat cu 6 noduri oricare doua noduri x, y sunt adiacente daca si numai daca

x mod 2=y mod 2

x%2==y%2

Care este numarul de componente conexe din graf?

a.

1

b.

6

c.

3

d.

2

32.           

V_21_I_6. Matricea de adiacenta alaturata corespunde unui graf neorientat care NU este de tip:

0 1 0 0 1

1 0 1 1 0

0 1 0 1 1

0 1 1 0 1

1 0 1 1 0

a.

ciclic

b.

hamiltonian

c.

eulerian

d.

conex

33.           

V_68_I_7.Se considera graful neorientat G = (X, U) unde X = si U = . Identificati care este numarul minim de noduri care trebuie eliminate pentru a se obtine un subgraf eulerian al lui G.

a.

0

b.

2

c.

1

d.

3

34.           

V_38_I_1. Daca un graf neorientat are n noduri si p componente conexe atunci numarul minim de muchii care trebuie adaugate astfel incat graful sa devina conex este:

a.

p

b.

p-1

c.

n-1

d.

n

35.           

V_76_I_2. Se considera un graf neorientat cu 9 noduri si muchiile [1,2], [4,8], [5,9], [2,3],[7,8], [3,7], [6,9], [6,7], [4,6], [4,5], [1,7]. Numarul minim de muchii care trebuie adaugate pentru ca graful sa devina eulerian este:

a.

5

b.

0

c.

25

d.

2

36.           

V_69_I_2. Se considera graful neorientat din figura alaturata:

Care este numarul cel mai mic de muchii care trebuie adaugate pentru ca graful sa devina eulerian ?

a.

3

b.

2

c.

4

d.

1

37.           

V_71_I_5.Precizati care este numarul minim de muchii care trebuie adaugate grafului din figura alaturata, astfel incat acesta sa devina eulerian.

a.

0

b.

4

c.

2

d.

1

38.           

V_73_I_2. Se considera graful neorientat cu 7 noduri si muchiile: [1,2], [1,4], [1,5], [1,7], [2,3],,7], [3,4], [3,5], [3,7], [4,5], [5,6], [6,7].Care este numarul minim de muchii ce trebuie inlaturate din graf astfel incat sa devina eulerian?

a.

3

b.

2

c.

1

d.

4

39.           

V_25_I_5. Se considera graful neorientat din figura alaturata. Cate grafuri partiale distincte, diferite de el insusi, fara varfuri izolate, se pot obtine?

Doua grafuri sunt distincte daca matricele lor de adiacenta sunt diferite.

a.

3

b.

13

c.

5

d.

4

40.           

V_72_1_8. Specificati care este numarul maxim de muchii care pot fi eliminate din graful alaturat, astfel incat acesta sa-si mentina proprietatea de graf hamiltonian

a.

4

b.

2

c.

1

d.

3

41.           

V_33_I_3. Dintr-un graf neorientat cu 6 noduri si 5 muchii, se obtine un graf partial prin suprimarea a doua muchii. Matricea de adiacenta asociata grafului partial astfel obtinut, va avea:

a.

6 linii si 3coloane

b.

4 linii si 4 coloane

c.

6 linii si 4 coloane

d.

6 linii si 6 coloane

42.           

V_33_I_8. Un graf neorientat este reprezentat cu ajutorul listelor de adiacenta alaturate. Acest graf are:

1:(3,5);

2:(4);

3:(1,5);

4:(2);

5:(3);

6:(7);

7:(6);

8:

a.

2 componente conexe si un nod izolat

b.

1 componenta conexa

c.

4 componente conexe

d.

3 componente conexe

43.           

V_55_I_4. Fie G un graf neorientat conex cu 20 de varfuri.Care este numarul minim de muchii ale grafului G?

a.

20

b.

10

c.

19

d.

190

44.           

V_35_I_1. Graful neorientat cu 8 noduri numerotate de la 1 la 8, este reprezentat cu ajutorul matricei de adiacenta alaturate. Numarul minim de muchii ce trebuie adaugate pentru ca nodul 2 sa fie legat prin lanturi elementare de lungime 3 de toate nodurile grafului, este:

a.

4

b.

5

c.

2

d.

3

45.           

V_35_I_3. Se da un graf neorientat cu 75 de noduri numerotate de la 1 la 75, si muchiile [21,40], [30,38], [21,30], [60,75]. Atunci numarul de componente conexe ale grafului este:

a.

69

b.

71

c.

2

d.

73

46.           

V_36_I_7. Cate grafuri neorientate distincte cu trei noduri numerotate de la 1 la 3 au muchie intre nodul 1 si nodul 2 ? Doua grafuri se considera distincte daca matricele lor de adiacenta sunt diferite.

a.

2

b.

4

c.

5

d.

8

47.           

V_37_I_4. Cate grafuri neorientate distincte cu n noduri numerotate 1,2n au muchie intre nodul 1 si nodul 2? Doua grafuri se considera distincte daca matricele lor de adiacenta sunt diferite.

a.

2n(n-1)/2 -1

b.

2n(n+1)/2

c.

2n(n-1)/2

d.

2n(n-1)/2 -1

48.           

V_39_I_1. Numim graf complementar al unui graf neorientat G graful neorientat G1 cu aceasi multime a nodurilor ca si G si cu proprietatea ca doua noduri sunt adiacente in G1 daca si numai daca nu sunt adiacente in G. Daca G are n noduri si m muchii , cate muchii are G1?

a.

exact n(n-1)/2 -m

b.

minimum n(n-1)/2 -m

c.

maximum n(n-1)/2 -m

d.

exact n-m

49.           

V_40_I_5. Numarul maxim de muchii dintr-un graf neorientat cu 6 noduri si 4 componente conexe este:

a.

4

b.

1

c.

3

d.

2

50.           

V_51_I_6. Care este numarul grafurilor partiale ale unui graf neorientat cu n varfuri si m muchii ?

a.

n!

b.

2n

c.

m!

d.

2m

51.           

V_52_I_2. Se considera un graf neorientat cu 7 varfuri astfel incat intre oricare doua varfuri distincte exista muchie. Cate lanturi elementare distincte, care au lungimea 3, extremitatea initiala varful 1 si extremitatea finala varful 7, exista?

a.

10

b.

42

c.

21

d.

20

52.           

V_52_I_3. Se considera un graf neorientat cu 10 varfuri si 37 de muchii.Care dintre urmatoarele afirmatii este adevarata?

a.

Graful este complet.

b.

Suma elementelor matricei de adiacenta asociata grafului este egala cu 37.

c.

Toate varfurile grafului au gradul 1.

d.

Graful nu are varfuri izolate.

53.           

V_53_I_1. Se considera un graf neorientat cu 10 varfuri cu proprietatea ca exista muchie de la varful i la varful j daca si numai daca i si j sunt numere prime (numarul 1 se considera ca nu este prim). Care este numarul muchiilor din acest graf?

a.

7

b.

6

c.

9

d.

12

54.           

V_13_I_6. Care dintre urmatoarele grafuri este un graf eulerian, dar nu este hamiltonian? Grafurile sunt precizate prin numarul n de noduri si multimea U a muchiilor.

a.

n=3, U=

b.

n=4, U=

c.

n=5, U=

d.

nici unul din grafurile anterioare.

55.           

V_14_I_1. Care este numarul maxim de componente conexe pe care le poate avea un graf neorientat cu 6 noduri si 5 muchii?

a.

4

b.

2

c.

1

d.

3

 

56.           

V_15_I_1. Fie graful neorientat cu 5 noduri si cu urmatoarele muchii: [1,2], [1,3], [3,4], [3,5], [4,5]. Care este numarul minim de muchii ce trebuie adaugate grafului astfel incat, in graful obtinut toate nodurile sa aiba acelasi grad?

a.

4

b.

5

c.

6

d.

3

 

57.           

V_23_I_5. Care este numarul maxim de muchii care pot fi eliminate astfel incat graful partial obtinut sa nu contina noduri izolate?

a.

4

b.

5

c.

2

d.

3

58.           

V_44_I_4. Fie graful neorientat G cu n varfuri etichetate cu numere de la 1 la n si avand proprietatea ca intre oricare doua varfuri distincte i si j, (1≤i≤n, 1≤j≤n), exista muchie daca si numai daca i+j=n. Precizati numarul componentelor conexe ale grafului G.

S-a folosit notatia [x] pentru partea intreaga a numarului x.

a.

n*(n-1)/2

b.

[(n+1)/2]

c.

n-1

d.

[n/2]+1

 

59.           

V_45_I_4. Graful neorientat G cu n varfuri si m muchii are varfurile etichetate cu x1,x2, x3,,xn. Care dintre urmatoarele afirmatii este corecta, daca s-a notat cu d(xi) gradul varfului xi?

a.

d(x1)+d(x2)+d(x3)++d(xn)=m-n

b.

d(x1)+d(x2)+d(x3)++d(xn)=m-1

c.

d(x1)+d(x2)+d(x3)++d(xn)>n*(n-1)

d.

d(x1)+d(x2)+d(x3)++d(xn) este un numar par

60.           

V_41_I_5. Fie un graf neorientat cu n varfuri (n>1). Cate valori 1 apar in matricea de adiacenta a grafului daca exista muchie intre oricare doua varfuri distincte?

a.

n*(n-1)/2

b.

n2

c.

0

d.

n*(n-1)

 

61.           

V_16_I_3. Un graf neorientat cu n noduri, cu n numar impar mai mare decat 2, in care fiecare nod are gradul n-1, este intotdeauna:

 

a.

graf aciclic (graf care nu contine nici un ciclu)

b.

arbore

 

c.

graf neconex

d.

graf eulerian

 

62.           

V_86_I_2. Se considera graful neorientat reprezentat prin matricea de adiacenta alaturata; atunci graful este

0 1 1 1 0

1 0 1 0 1

1 1 0 0 0

1 0 0 0 1

0 1 0 1 0

a.

eulerian

b.

aciclic (nu contine niciun ciclu)

c.

arbore

d.

hamiltonian

63.           

V_32_I_7. Se considera graful neorientat: G=(X,U) cu X= si U=. Care dintre urmatoarele succesiuni  de noduri reprezinta un lant hamiltonian in graful dat?

a.

(7, 6, 3, 5, 4, 2, 1)

b.

(1, 2, 3, 4, 5, 6, 7)

c.

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

d.

(4, 5, 3, 6, 7)

64.           

V_22_I_3. Care este numarul minim de muchii care trebuie eliminate astfel incat graful alaturat sa devina eulerian?

a.

2

b.

3

c.

1

d.

0

 

65.           

V_17_I_3. Un graf neorientat este eulerian daca:

a.

este conex si contine cel putin un ciclu elementar

b.

contine un singur ciclu elementar

c.

este conex si suma elementelor de pe fiecare coloana a matricei de adiacenta este numar par

d.

contine cel putin un ciclu hamiltonian

66.           

V_89_I_7. Se considera graful neorientat dat prin matricea de adiacenta alaturata. Care este numarul maxim de noduri ale unui subgraf eulerian al grafului dat?

0 1 1 0 0 0 1

1 0 1 1 0 0 1

1 1 0 0 0 1 0

0 1 0 0 1 0 1

0 0 0 1 0 1 0

0 0 1 0 1 0 0

1 1 0 1 0 0 0

a.

6

b.

3

c.

5

d.

4

67.           

V_18_I_7. Care este numarul minim de muchii care pot fi eliminate din graful neorientat, dat prin listele de adiacenta alaturate, astfel incat graful sa devina eulerian?

1:(2,3,5)

2:(1,4)

3:(1,4,5)

4:(2,3,5)

5:(1,3,4)

a.

1

b.

2

c.

3

d.

0

68.           

V_57_I_8.Considerand un graf neorientat G cu 5 noduri si matricea de adiacenta data alaturat, stabiliti care dintre urmatoarele afirmatii nu este adevarata:

0 1 1 1 1

1 0 0 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

a.

G este eulerian

b.

G este conex

c.

G nu este hamiltonian

d.

G este aciclic

69.           

V_58_I_8.Considerand un graf neorientat G cu 5 noduri, dat prin matricea de adiacenta alaturata, stabiliti care dintre urmatoarele afirmatii este adevarata:

0 1 1 1 1

1 0 1 0 0

1 1 0 0 0

1 0 0 0 1

1 0 0 1 0

a.

G nu este conex

b.

G este eulerian

c.

G este aciclic

d.

G este hamiltonian

 

70.           

V_59_I_3.Considerand un graf neorientat G cu 5 noduri dat prin matricea de adiacenta alaturata, stabiliti care dintre urmatoarele afirmatii este adevarata:

0 1 1 0 1

1 0 1 0 0

1 1 0 0 0

0 0 0 0 1

1 0 0 1 0

a.

G este aciclic

b.

G este conex

c.

G este eulerian

d.

G este hamiltonian

71.           

V_62_I_7. Numarul minim de muchii care trebuie adaugate grafului din desenul alaturat pentru a deveni eulerian este:

a.

5

b.

2

c.

4

d.

3


7.2.           Grafuri orientate - Teste grila

1.               

V_93_I.5. Se considera graful orientat cu 5 noduri numerotate de la 1 la 5 si cu arcele: (1,2),(2,1),(2,5),(3,2),(4,3),(5,1),(5,2),(5,4). Determinati gradul intern al nodului cu gradul extern maxim.

a.

3

b.

1

c.

2

d.

0

2.               

V_18_I_3. Suma gradelor interne ale tuturor varfurilor unui graf orientat este totdeauna egala cu:

a.

numarul valorilor de 1 aflate sub diagonala principala in matricea de adiacenta

b.

suma tuturor valorilor aflate deasupra diagonalei principale in matricea de adiacenta

c.

produsul gradelor externe ale tuturor varfurilor grafului

d.

suma gradelor externe ale tuturor varfurilor grafului

3.               

V_12_I_3. Un graf orientat este reprezentat prin matricea de adiacenta data alaturat. Precizati care sunt nodurile pentru care gradul interior este mai mare decat gradul exterior.

0 1 1 0 0 0

0 0 1 1 0 1

1 1 0 1 0 0

0 0 0 0 1 0

0 1 0 0 0 0

0 1 0 0 1 0

a.

2, 4, 5

b.

2, 4, 5, 6

c.

1, 4, 5

d.

1, 3, 6

 

4.               

V_15_I_8. Numarul de grafuri orientate cu n varfuri este:

a.

b.

c.

d.

 

5.               

V_43_I_6. Fie graful orientat reprezentat in figura alaturata. Cate dintre varfurile grafului au gradul intern egal cu 2?

a.

3

b.

1

c.

0

d.

2

6.               

V_97_I_7. Gradul intern pentru nodul cu eticheta i dintr-un graf orientat la care se cunoaste matricea de adiacenta este egal cu numarul de cifre egale cu 1 aflate pe:

a.

linia i

c.

diagonala secundara

b.

diagonala principala

d.

coloana i

7.               

V_42_I_2. Fie G un graf orientat cu 6 varfuri dat prin matricea de adiacenta alaturata. Precizati cate dintre varfurile grafului au gradul intern egal cu gradul extern?

0 0 0 0 1 0

1 0 0 1 0 1

0 0 0 0 0 0

1 0 0 0 1 0

0 1 0 0 0 0

0 0 0 0 1 0

a.

2

b.

1

c.

4

d.

3

 

8.               

V_26_I_6.Considerand graful orientat din figura alaturata, stabiliti cate dintre varfurile grafului au gradul extern (exterior) egal cu dublul gradului intern (interior).

a.

2

b.

1

c.

0

d.

3

9.               

V_27_I_7. Considerand graful orientat din figura alaturata, stabiliti cate dintre varfurile grafului au gradul extern (exterior) egal cu gradul intern (interior).

a.

2

b.

3

c.

1

d.

0

10.           

V_28_I_1.Intr-un graf orientat cu 10 varfuri numerotate de la 1 la 10 exista arce numai intre perechile de varfurile i si j, i≠j cu proprietatea ca i este divizor al lui j (i fiind extremitatea initiala si j extremitatea finala a arcului). Numarul de valori egale cu 1 din matricea de adiacenta corespunzatoare grafului este:

 

 

a.

17

b.

10

c.

30

d.

34

11.           

V_30_I_6. Graful orientat G=(X,U) are 20 de varfuri numerotate de la 1 la 20 si arce intre varfurile numerotate i si j care indeplinesc conditiile: i este numar de o singura cifra iar j este un numar de doua cifre ce are in scrierea sa cifra i. Numarul valorilor de 1 din matricea de adiacenta asociata grafului G este:

a.

20

b.

19

c.

10

d.

15

12.           

V_98_I_2. Care e numarul minim de arce pe care trebuie sa le contina un graf cu 5 varfuri care astfel incat oricum ar fi acestea plasate sa existe cel putin un drum intre oricare doua varfuri.

a.

10

b.

9

c.

20

d.

17

13.           

V_11_I_5. Se considera graful orientat dat prin matricea de adiacenta alaturata. Care este lungimea maxima a unui drum elementar de la varful 1 pana la varful 5?

0 1 1 0 0 0

0 0 0 1 1 1

0 0 0 0 0 0

0 0 1 0 0 1

0 0 1 0 0 0

0 1 0 0 1 0

a.

4

b.

3

c.

1

d.

5

 

14.           

V_96_I_7. Care dintre urmatoarele arce trebuie adaugat unui graf orientat cu 5 noduri si cu matricea de adiacenta alaturata astfel incat in acest graf sa existe cel putin un drum intre oricare doua varfuri?

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

 

 

a.

(3 , 5)

b.

(4 , 1)

c.

(5 , 3)

d.

(3 , 2)

15.           

V_99_I_2. Matricea de adiacenta a unui graf orientat cu 8 noduri si 16 arce este simetrica fata de diagonala principala. Care dintre urmatoarele afirmatii este adevarata pentru acest graf?

a.

Fiecare nod al grafului are gradul interior diferit de gradul exterior

b.

Fiecare nod al grafului are gradul interior egal cu gradul exterior

c.

Numarul de valori egale cu 1 din matricea de adiacenta este impar

d.

Graful nu contine nici un drum

16.           

V_100_I_4. Pentru un graf orientat dat, notam cu Se suma gradelor exterioare ale tuturor nodurilor grafului si cu Si suma gradelor interiore ale tuturor nodurilor grafului. Care dintre urmatoarele relatii matematice este adevarata?

a.

Se≠Si

b.

Se=Si

c.

Se<Si

d.

Se>Si

17.           

V_10_I_7. Fie G=(V,E) un graf orientat in care multimea nodurilor este V=, iar multimea arcelor este E= (prin a mod b am notat restul impartirii lui a la b). Stabiliti care dintre urmatoarele afirmatii este adevarata:

a.

Pentru oricare pereche de noduri i si j (i≠j) exista cel putin un drum de la i la j si cel putin un drum de la j la i

b.

pentru orice nod al grafului G suma dintre gradul interior si gradul exterior este nenula

c.

toate varfurile grafului G au gradul interior egal cu gradul exterior

d.

graful G contine circuite

 

18.           

V_9_I_2. Fie graful orientat G=(V,E) unde multimea nodurilor este V=, iar multimea arcelor este E=. Numarul nodurilor grafului G care au gradul exterior egal cu 0 este:

 

a.

1

b.

3

c.

0

d.

2

19.           

V_8_I_3. Considerand graful orientat G cu 6 noduri reprezentat prin intermediul listelor de adiacenta alaturate, stabiliti cate dintre varfurile sale au gradul intern egal cu gradul extern:

1: 5

2: -

3: 2 4

4: 2 3

5: 2 4

6: 1 2 3 4 5

 

 

a.

4

b.

1

c.

3

d.

2

20.           

V_6_I_5. Cate dintre nodurile grafului orientat cu 6 noduri si cu matricea de adiacenta alaturata au gradul interior egal cu gradul exterior?

0 1 0 0 0 0

1 0 1 0 0 1

0 0 0 1 0 1

0 1 1 0 1 0

0 0 0 1 0 1

1 0 1 1 0 0

a.

2

b.

1

c.

4

d.

3

21.           

V_16_I_7. Lungimea unui drum elementar intr-un graf orientat cu n varfuri poate fi:

a.

b.

n+1

c.

n

d.

n-1

 

22.           

V_44_I_2. Fie graful orientat cu 5 varfuri reprezentat prin matricea de adiacenta alaturata.

Care este marimea celui mai lung drum elementar din graf?

0 0 0 1 1

0 0 1 0 1

0 0 0 0 0

0 1 1 0 0

0 0 0 0 0

a.

2

b.

1

c.

3

d.

4

 

23.           

V_45_I_6. Fie graful orientat G cu 5 noduri, reprezentat prin matricea de adiacenta alaturata. Precizati lungimea celui mai mare drum elementar din graful G?

0 1 1 0 0

0 0 0 1 0

0 1 0 1 0

0 0 0 0 0

1 0 0 1 0

a.

5

b.

3

c.

2

d.

4

 

24.           

V_14_I_5. Fie graful orientat cu 5 varfuri si urmatoarele arce: [1,2], [1,4], [3,1], [3,2], [4,5], [4,2], [5,1]. Cate circuite contine acest graf?

a.

3

b.

4

c.

2

d.

1

 

25.           

V_35_I_8. Se considera un graf orientat cu 6 varfuri si arcele: (1,4), (1,5), (2,3), (2,4), (3,4), (4,3), (4,6), (5,4), (6,4). Gradul interior al varfului 4 este:

a.

7

b.

3

c.

2

d.

5

26.           

V_21_I_1. Care este numarul minim de arce care trebuie adaugate grafului orientat din figura alaturata astfel incat oricare doua varfuri sa fie unite prin drumuri elementare?

a.

1

b.

3

c.

0

d.

2

27.           

V_31_I_7. Se considera graful orientat cu 8 noduri, definit cu ajutorul listelor de adiacenta alaturate. In acest graf, nodul 1 este legat prin drumuri de lungime 2 de nodurile:

1: 4, 5, 6

2: 3, 4

3: 4

4: 3, 6

5: 4, 1

6: 1, 4

7: 1, 8

8:

a.

7,8

b.

5,6,4

c.

3,4,6

d.

2

28.           

V_34_I_7. Un graf orientat, este memorat cu ajutorul listelor alaturate de adiacenta. Numarul nodurilor care au gradul interior egal cu gradul exterior este:

1: 5

2: 4

3: 5

4: 1, 2

5: 2, 3, 4

a.

2

b.

4

c.

1

d.

3

29.           

V_36_I_3. Se considera graful orientat dat prin matricea de adiacenta alaturata, ale carui noduri sunt numerotate de la 1 la 4 corespunzator liniilor matricei. Sa se determine care sunt nodurile care au gradul intern egal cu 2 :

0 0 0 1

1 0 0 0

1 1 0 0

0 1 1 0

a.

nici nodul 1 si nici nodul 2

b.

atat nodul 1 cat si nodul 2

c.

numai nodul 2

d.

numai nodul 1

30.           

V_37_I_6. Un graf orientat are cinci noduri numerotate cu 1, 2, 3 ,4, 5 si patru arce: [1,2], [2,1], [2,3], [3,4]. Prin eliminarea nodului 2 si a arcelor incidente cu acesta obtinem:

a.

un subgraf cu patru noduri si un arc

b.

un subgraf cu doua noduri si niciun arc

c.

un graf partial

d.

un subgraf cu cinci noduri si trei arce

31.           

V_39_I_6. Care dintre urmatoarele secvente de noduri reprezinta un drum in graful orientat dat prin matricea de adiacenta alaturata, stiind ca nodurile sunt numerotate de la 1 la 5 corespunzator liniilor si coloanelor tabloului?

0 1 0 0 0

0 0 0 1 0

0 0 0 0 0

0 1 1 0 0

0 0 0 1 0

a.

1,5,4,3

b.

1,2,4,3

c.

5,4,3,1

d.

2,4,3,1

32.           

V_38_I_4. Intr-un graf orientat cu n noduri, gradul extern al unui varf poate fi maximum:

a.

n-1

b.

1

c.

n+1

d.

2

33.           

V_63_I_3. Intr-un graf orientat G(X,V) cu 6 noduri numerotate cu numere distincte de la 1 la 6, exista arc de la nodul i la nodul j daca si numai daca i<j si j-i>1. Numarul de noduri din graf care au gradul interior mai mare decat gradul exterior este:

a.

3

b.

0

c.

2

d.

1

34.           

V_64_I_2. Pentru un graf orientat G(X,V) cu n noduri numerotate cu numerele distincte 1,2,..,n, si reprezentat prin matricea de adiacenta a, secventa de instructiuni alaturata descrisa in limbajul pseudocod determina in variabila nr:

nr0

citeste k

┌pentru i1,n executa

│┌daca aki=1 atunci

││ nr nr+1

│└■

└■

a.

gradul nodului k

b.

gradul exterior al nodului k

c.

gradul interior al nodului k

d.

numarul de elemente egale cu 1 din matricea de adiacenta

35.           

V_65_I_5. Graful orientat G cu 10 noduri, reprezentat prin listele de adiacenta alaturate, are:

1: 4 6

2: 1

3:

4: 6

5: 7 9

6:

7:

8:

9: 8

10:

a.

Doua drumuri distincte de la nodul 2 la nodul 6

b.

Un drum de la nodul 7 la nodul 8

c.

Un circuit care contine nodurile 1,4,6

d.

Doua drumuri distincte de la nodul 5 la nodul 8

36.           

V_40_I_7. Matricea drumurilor unui graf orientat este o matrice de dimensiune nxn, definita astfel:

aij=1 daca exista cel putin un drum de la nodul i la nodul j si, respectiv aij=0 daca nu exista niciun drum de la i la j. Care este matricea drumurilor pentru graful alaturat?

a.

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

0 0 0 1 1

0 0 0 1 1

b.

0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

0 0 0 0 1

0 0 0 1 0

c.

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

0 0 1 1 1

0 0 0 1 1

d.

0 1 0 0 0

0 0 1 0 0

1 0 0 1 0

0 0 0 0 1

0 0 0 1 0

37.           

V_51_I_2. Consideram un graf orientat cu n varfuri si m arce . Ce valoare se obtine prin insumarea elementelor matricei de adiacenta asociata grafului?

a.

n

b.

2*m

c.

m/2

d.

m

38.           

V_95_I_6.Se considera graful orientat cu 5 noduri, numerotate de la 1 la 5, reprezentat cu ajutorul matricei de adiacenta alaturata. Ce arc trebuie adaugat astfel incat graful sa contina cel putin un circuit elementar de lungime 5?

0 1 0 0 0

1 0 0 0 0

0 1 0 1 0

1 0 0 0 0

0 1 1 0 0

a.

(5,2)

b.

(5,4)

c.

(4,5)

d.

(2,5)

39.           

V_47_I_6. Se considera graful orientat dat prin matricea de adiacenta alaturata.

Stabiliti care dintre urmatoarele afirmatii este adevarata.

0 1 1 0

0 0 0 0

0 1 0 1

0 0 0 0

a.

graful contine un circuit

 

b.

exista noduri cu gradul intern egal cu gradul extern

 

c.

graful contine un singur varf cu gradul intern 0

 

d.

graful nu contine niciun drum elementar (un drum se numeste elementar daca varfurile din componenta sa sunt distincte)

 

40.           

V_58_I_7. Consideram un graf orientat G cu 4 noduri si cu gradele externe ale acestora: 2,1,0,2 Care dintre variantele urmatoare poate reprezenta sirul gradelor interne ale lui G?

a.

1,1,1,1

b.

1,1,3,0

c.

1,1,2,2

d.

1,3,2,0

41.           

V_88_I_7. Se considera graful orientat G=(V, E) unde V= si E=. Care este numarul maxim de arce dintr-un drum elementar al grafului (drum cu noduri distincte)?

a.

3

b.

6

c.

4

d.

5

42.           

V_89_I_2. Fie graful orientat cu nodurile numerotate cu numerele distincte 1,2,3,4,5 si care contine arcele: (1,2),(1,4),(1,5),(5,4),(4,3), (3,2),(3,1). Care din urmatoarele succesiuni reprezinta un drum elementar (cu toate nodurile distincte)?

a.

1,2,3

b.

1,5,4,3,2

c.

3,1,4,3,2

d.

1,2,5,4,3

43.           

V_49_I_6. Fie graful orientat G cu n=6 noduri dat prin listele de adiacenta: 1: (2,3,4), 2: (3, 5), 3: (2, 4), 4: (5), 5: (6), 6: (4). Care este lungimea celui mai scurt drum de la nodul 1 la nodul 6?

a.

2

b.

3

c.

1

d.

4

 

44.           

V_46_I_1. Fie graful orientat G cu n=5 noduri, dat prin urmatoarele liste de adiacenta: 1: (2, 3), 2: (3, 4), 3: (4, 5), 4: (1, 2), 5: (4).

Care dintre urmatoarele propozitii este falsa?

a.

exista cel putin un nod in graful G care are gradul intern egal cu cel extern

b.

exista cel putin un drum intre oricare doua noduri ale grafului G

c.

graful G nu are circuite

d.

graful G are 9 arce

45.           

V_49_I_4. Care este numarul minim de arce ce trebuie eliminate astfel incat graful din desenul alaturat sa nu contina niciun circuit?

a.

1

b.

3

c.

0

d.

2

 

46.           

V_50_I_8. Care este numarul de circuite elementare distincte in graful din figura din dreapta? (Doua circuite elementare sunt distincte daca difera prin cel putin un arc.)

a.

4

b.

3

c.

0

d.

2

 

47.           

V_2_I_2. Se considera un graf orientat cu 6 noduri numerotate cu 1, 2,,6 si cu multimea arcelor formata doar din arcele:

        de la fiecare nod numerotat cu un numar neprim i (i>1) la toate nodurile numerotate cu numere ce apartin multimii divizorilor proprii ai lui i (divizori diferiti de 1 si de i);

        de la nodul numerotat cu 1 la nodul numerotat cu 2;

        de la fiecare nod numerotat cu un numar prim i la nodul numerotat cu i+1.

Stabiliti care este numarul de circuite elementare distincte continute de graful din enunt. (Doua circuite sunt distincte daca difera prin cel putin un arc).

a.

1

b. 2

c. 3

d. 0

48.           

V_4_I_6. Un graf orientat are 8 arce si fiecare nod al grafului are gradul interior un numar nenul. Doar doua dintre noduri au gradul interior un numar par, restul nodurilor avand gradele interioare numere impare. Care este numarul maxim de noduri pe care poate sa le aiba graful?

a.

7

b.

8

c.

5

d.

6

49.           

V_3_I_5. Se considera un graf orientat cu 6 noduri numerotate cu 1, 2,,6 si cu multimea arcelor formata doar din arcele:

        de la fiecare nod numerotat cu numar neprim i (i>1) la toate nodurile numerotate cu numere ce apartin multimii divizorilor proprii ai lui i (divizori diferiti de 1 si i);

        de la nodul numerotat cu 1 la nodul numerotat cu 2;

        de la fiecare nod numerotat cu un numar prim i la nodul numerotat cu i+1.

Stabiliti cate noduri din graf au suma dintre gradul intern si cel extern egala cu 3.

a.

1

b.

6

c.

2

d.

0

50.           

V_5_I_5. Un graf orientat are 8 arce si fiecare nod al grafului are gradul exterior un numar nenul. Doar doua dintre noduri au gradul exterior un numar impar, restul avand gradele exterioare numere pare. Care este numarul maxim de noduri pe care le poate avea graful?

a.

4

b.

8

c.

3

d.

5

51.           

V_81_I_1. Fie graful orientat cu 5 noduri si arcele (1,2), (1,5), (2,5), (2,4), (3,2), (4,3), (4,5). Care este numarul minim de arce care trebuie adaugate grafului astfel incat sa existe cel putin un drum intre oricare doua varfuri?

a.

1

b.

0

c.

3

d.

2

52.           

V_82_I.3. Un graf orientat are 11 varfuri numerotate de la 1 la 11. Intre oricare doua varfuri ale sale, x si y (x y), exista atat arcul de la x la y cat si arcul de la y la x daca si numai daca restul impartirii lui x la 3 este egal cu restul impartirii lui y la 3. Care este numarul minim de arce care trebuie adaugate acestui graf astfel incat sa existe cel putin un drum intre oricare doua varfuri ale sale.

a.

6

b.

4

c.

2

d.

3

53.           

V_83_I_1. Se considera graful orientat din figura alaturata. Cate circuite elementare disticte are graful?

a.

4

c.

1

b.

3

d.

2

54.           

V_84_I_7. Se considera graful orientat din figura alaturata. Cate perechi de varfuri de forma (x,y), cu x<y, respecta proprietatea ca exista cel putin un drum de la x la y si cel putin un drum de la y la x?

a.

10

c.

6

b.

4

d.

8

55.           

V_90_I_7. Fie un graf orientat dat care are 5 varfuri numerotate 1,2,3,4,5 si arcele: (2,1), (2,3), (2,4), (3,4), (1,5), (5,4). Numarul circuitelor elementare distincte (care difera prin cel putin un arc) din graful din enunt este egal cu:

a.

3

b.

0

c.

2

d.

1

56.           

V_94_I_7. Se considera graful orientat dat prin matricea de adiacenta alaturata, graf cu 6 noduri numerotate de la 1 la 6 corespunzator liniilor si coloanelor matricei. Care dintre urmatoarele este o pereche de noduri i j astfel incat exista un drum elementar de la i catre j?

0 0 1 0 0 1

1 0 0 0 1 0

0 0 0 1 0 0

0 0 1 0 0 0

0 1 0 0 0 0

1 0 0 0 0 0

a.

6 5

b.

5 4

c.

4 6

d.

4 5

57.           

V_69_I_4.Se considera graful orientat G = (X, U) unde X = si U = . Identificati care sunt nodurile accesibile din toate celelalte noduri ale grafului prin intermediul unor drumuri elementare.

a.

6

b.

1 5

c.

1 2 3 5

d.

4 5

58.           

V_19_I_1.Graful neorientat reprezentat prin listele de adiacenta alaturate se transforma in graf orientat astfel: fiecare muchie [i,j], cu i<j, devine arcul (i,j). In graful orientat astfel obtinut lungimea celui mai scurt drum de la varful 1 la varful 5 este:

1:(2,3)

2:(1,3,5)

3:(1,2,4)

4:(3,5)

5:(2,4)

a.

4

b.

1

c.

2

d.

3

 

59.           

V_66_I_2. Se considera un graf orientat dat prin matricea de adiacenta alaturata. Stabiliti care este numarul nodurilor din graf care au proprietatea ca diferenta absoluta a gradelor (intern si extern) este egala cu 1 ?

0 1 0 0 1

0 0 1 1 0

1 0 0 0 0

0 0 1 0 1

0 1 0 0 0

a.

4

b.

3

c.

2

d.

5

 

60.           

V_77_I_3 Fie graful orientat cu 8 varfuri si arcele [1,2], [2,3], [3,1], [4,5], [5,6],[5,7],[6,7],[7,4],[8,7]. Numarul de varfuri cu proprietatea ca gradul interior este egal cu gradul exterior este:

 

 

a.

2

b.

7

c.

0

d.

5

61.           

V_78_I_8.Fie graful orientat cu 7 varfuri, numerotate de la 1 la 7 si listele de adiacenta L1=, L2=, L3=, L4=, L5=, L6=, L7=. Care este varful (care sunt varfurile) cu gradul interior maxim?

a.

3,6,7

b.

1

c.

2

d.

4

62.           

V_67_I_3.Se considera graful orientat dat prin matricea de adiacenta alaturata.

Stabiliti cate dintre nodurile grafului au gradul interior (intern) egal cu gradul exterior (extern).

0 1 0 1 0

0 0 0 0 1

0 1 0 0 0

0 1 1 0 0

0 1 0 1 0

 

 

a.

2

b.

1

c.

0

d.

3

63.           

V_68_I_2.Consideram un graf orientat cu nodurile numerotate cu numere distincte 1, 2, 3, Graful este reprezentat printr-o matrice de adiacenta A.

Precizati care este semnificatia sumei valorilor dintr-o coloana oarecare x a matricei A.

a.

reprezinta numarul arcelor care sosesc in nodul numerotat cu numarul x

b.

reprezinta numarul drumurilor care nu trec prin nodul numerotat cu numarul x

c.

reprezinta numarul drumurilor care trec prin nodul numerotat cu numarul x

d.

reprezinta numarul arcelor care pleaca din nodul numerotat cu numarul x

64.           

V_69_I_4.Se considera graful orientat G = (X, U) unde X = si U = . Identificati care sunt nodurile accesibile din toate celelalte noduri ale grafului prin intermediul unor drumuri elementare.

a.

6

b.

1 5

c.

1 2 3 5

d.

4 5

65.           

V_70_I_2. Se considera graful orientat G=(X,U) unde X= si U=.

Care sunt nodurile legate de nodul 2 prin drumuri a caror lungime este egala cu cea a drumului de lungime minima dintre nodurile 2 si 6 ?

a.

7 4

b.

8 2

c.

5 8 9

d.

1 5 3

66.           

V_71_I_2.Precizati care dintre nodurile grafului orientat a carui matrice de adiacenta este reprezentata alaturat, au gradul interior egal cu gradul exterior.

0 1 0 0 0 0 0 0

0 0 1 0 0 0 1 0

0 0 0 1 1 1 0 0

0 0 0 0 0 0 1 0

0 0 0 1 0 0 1 0

0 1 0 1 1 0 0 0

1 0 1 0 0 1 0 0

0 0 0 0 0 0 0 0

a.

1,2,5,7,8

b.

1,2,5,6,8

c.

2,5,6,7,8

d.

1,2,5,7,6

67.           

V_73_I_5.Precizati care este lista de adiacenta corespunzatoare nodului 6, pentru graful orientat reprezentat prin matricea de adiacenta alaturata.

0 1 0 0 0 0

0 0 1 0 0 1

0 1 0 1 0 1

0 0 1 0 1 0

0 0 0 0 0 1

1 0 1 1 0 0

a.

1, 3, 4

b.

1, 3, 5

c.

2, 3, 5

d.

2, 3, 4

68.           

V_74_I_8. Se considera un graf orientat cu 8 noduri, numerotate de la 1 la 8 si arcele [1,2], [1,8], [2,3], [2,7], [3,2], [5,8], [6,5], [6,8], [7,3], [7,4], [8,6], [8,7]. Precizati care este nodul la care se poate ajunge, din oricare alt nod al grafului, parcurgand drumuri ale grafului.

a.

3

b.

4

c.

1

d.

2

69.           

V_75_I_7.Se considera graful orientat cu 6 noduri si arcele [1,2], [1,6], [2,1], [2,3], [2,4], [2,6], [3,2], [3,4], [3,5], [3,6], [4,3], [4,5], [4,6], [5,4], [6,5]. Cate drumuri elementare de la nodul 1 la nodul 6 exista?

a.

5

b.

8

c.

7

d.

6

70.           

V_91_I_2.Se considera graful orientat cu 6 noduri dat prin matricea de adiacenta alaturata. Stabiliti cate perechi neordonate de noduri (a,b) exista astfel incat exista drum fie de la a catre b, fie de la b catre a, dar nu amandoua. La numarare tineti cont de faptul ca, de exemplu, perechea neordonata (2,4) este una si aceeasi cu perechea (4,2).

0 1 0 0 1 0

1 0 0 1 0 0

0 1 0 0 1 1

0 1 0 0 0 0

1 1 0 0 0 0

0 0 1 1 0 0

a.

3

b.

8

c.

4

d.

6

71.           

V_92_I_3.Se considera un graf orientat cu 4 noduri etichetate cu numere de la 1 la 4 si cu arcele (1,2) (1,3) (2,1) (2,3) (2,4) (4,2) (4,3). Care dintre nodurile grafului au gradul interior mai mare decat gradul exterior?

a.

1, 2 si 4

b.

3

c.

3 si 4

d.

3 si 2

7.3.           Arbori - Teste grila

1.   

V_1_I_8. Care dintre urmatoarele matrice este matricea de adiacenta a unui arbore cu 4 noduri?

a.

0 1 0 1

0 0 1 0

1 0 0 0

1 0 1 0

b.

0 0 1 0

0 0 0 1

1 0 0 0

0 1 0 0

c.

0 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

d.

0 0 1 0

0 0 0 1

1 0 0 1

0 1 1 0

 

2.               

V_89_I_3. Se considera un arbore. Care dintre urmatoarele afirmatii este adevarata?

a.

are cel putin un nod izolat

b.

toate nodurile au grad par

c.

are cel putin doua componente conexe

d.

este aciclic

3. 

V_50_I_4. Fie graful neorientat dat prin matricea de adiacenta alaturata. Numarul de muchii ce trebuie eliminate pentru ca graful sa devina arbore este:

0 1 1 0 0 0 0

1 0 0 1 0 0 0

1 0 0 0 1 0 0

0 1 0 0 0 1 0

0 0 1 0 0 0 1

0 0 0 1 0 0 1

0 0 0 0 1 1 0

a.

2

c.

0

d.

1

b.

nu se poate obtine arbore prin eliminari de muchii

4.               

V_97_I_3. Numarul de noduri care au gradul 1 intr-un graf neorientat conex si aciclic cu n noduri (n>1) este:

a.

mai mare sau cel putin egal cu 2

b.

exact n-1

c.

exact 1

d.

0 sau 1

5.               

V_99_I_8. Fie arborele cu 8 noduri si cu muchiile [1,2], [1,3] , [1,4] , [4,5] , [6,4] , [1,8] , [4,7]. Cati vectori de tati distincti se pot construi pentru acest arbore? Doi vectori de tati sunt distincti daca in cei doi vectori exista cel putin o pozitie pentru care elementele din respectivele pozitii sunt distincte.

a.

40320

b.

7

c.

28

d.

8

6.  

V_32_I_2. Se considera graful neorientat G=(X,U) X= U=. Pentru a transforma graful intr-un arbore, putem elimina:

a.

muchiile [1,5] si [5,6]

b.

nodul 3 si muchiile incidente lui

c.

nodul 4 si muchiile incidente lui

d.

muchia [2,6]

7.               

V_9_I_4. Fie G un graf neorientat conex cu 100 de noduri si 2007 muchii. Numarul de muchii care trebuie eliminate din G astfel incat acesta sa devina arbore este:

a.

1237

b.

1907

c.

1007

d.

1908

8.               

V_8_I_7. Fie G=(V,E) un arbore in care V=.

Stiind ca si G=(V ,E) este deasemenea un arbore, stabiliti care dintre urmatoarele propozitii este adevarata (notatia |M| reprezinta numarul elementelor unei multimi M):

a.

|E|=|E|

b.

|E|=|E|+1

c.

|E|=|E|-1

d.

|E|=|E|+2

9.               

V_56_I_3. Prin inaltimea unui arbore cu radacina intelegem numarul de muchii ale celui mai lung lant elementar care are una dintre extremitati in radacina arborelui. Daca arborele T este dat prin urmatorul vector de tati: 4,5,1,0,4,5,6,1,4, atunci care este inaltimea sa?

a.

1

b.

2

c.

3

d.

4

10.           

V_60_I_8.Daca G este un graf neorientat cu proprietatea ca intre orice doua varfuri ale sale exista un unic lant elementar, atunci G este:

a.

graf eulerian

b.

arbore

c.

graf hamiltonian

d.

un graf cu toate gradele numere impare

11.           

V_88_I_2. Un arbore cu 10 noduri are urmatorul vectorul de tati: T=[4,4 2,5,0,5,8,6,8,8]. Cate noduri frunza (terminale) are acest arbore?

a.

5

b.

3

c.

4

d.

6

12.           

V_27_I_3.Se construieste un arbore in care nodul radacina memoreaza valoarea 20 iar fiecare nod neterminal are ca descendenti directi noduri in care se pastreaza divizorii proprii ai valorii din nodul parinte (numarul natural d este dizivor propriu al numarului natural a, daca d este divizor al numarului a si este diferit de 1 si de a). Cate noduri terminale (frunze) exista in arbore ?

a.

5

b.

3

c.

10

d.

7

13.           

V_90_I_3. Intr-un abore cu 50 noduri, numarul maxim de fii pe care poate sa ii aiba un nod al sau este:

a.

1

b.

49

c.

2

d.

0

14.           

V_61_I_6. Numarul minim de muchii care pot fi eliminate astfel incat graful din desenul alaturat sa devina arbore este:

a.

1

b.

3

c.

2

d.

0

15.           

V_21_I_4. Care dintre urmatoarele siruri de numere reprezinta gradele nodurilor unui arbore cu 5 noduri?

a.

1, 1, 3, 1, 0

b.

4, 1, 5, 1, 2

c.

4, 3, 2, 1, 1

d.

2, 1, 1, 3, 1

16.           

V_25_I_3. Numarul de noduri ale unui arbore cu 100 de muchii este:

a.

101

b.

99

c.

100

d.

50

17.           

V_63_I_6.Matricea de adiacenta asociata unui arbore cu p noduri contine:

a.

p2-2p+2 elemente nule

b.

p elemente nule

c.

p2-p elemente nule

d.

p-1 elemente nule

18.           

V_17_I_7. Care este gradul maxim posibil al unui nod dintr-un arbore cu n noduri?

a.

n-1

b.

n DIV 2 | n/2

c.

2

d.

n

19.           

V_24_I_6.Care dintre matricele de adiacenta de mai jos corespunde unui arbore cu 4 noduri?

a.

0 0 1 1

0 0 1 0

1 1 0 1

1 0 1 0

b.

0 0 1 0

0 0 1 0

1 1 0 0

0 0 0 0

c.

0 0 1 0

0 0 0 1

1 0 0 0

0 1 0 0

d.

0 0 1 0

0 0 1 0

1 1 0 1

0 0 1 0

20.           

V_82_I.7. Se considera arborele cu 8 noduri numerotate de la 1 la 8, dat prin lista de muchii: (1,2), (1,3), (3,4), (3,5), (3,6), (4,8), (4,7). Care dintre nodurile urmatoare poate fi radacina a acestui arbore astfel incat inaltimea lui sa fie maxima (inaltimea arborelui este egala cu numarul de muchii ale celui mai lung lant ce uneste radacina de fiecare frunza).

a.

1

b.

2

c.

4

d.

3

21.           

V_20_I_6. Un graf neorientat este graf complet daca si numai daca oricare doua noduri sunt adiacente. Care este numarul de muchii care trebuie eliminate dintr-un graf neorientat complet cu 8 noduri, astfel incat graful partial obtinut sa fie arbore?

a.

8

b.

21

c.

16

d.

20

 

22.           

V_42_I_4. Cate muchii trebuie sa eliminam dintr-un graf neorientat conex cu 12 varfuri si 21 de muchii astfel incat acesta sa devina arbore?

a.

9

b.

12

c.

10

d.

11

 

23.           

V_47_I_2. Cate cicluri elementare care difera prin cel putin o muchie se formeaza prin adaugarea unei singure muchii la un arbore (ciclul este elementar daca este format numai din noduri distincte, exceptie facand primul si utimul)?

a.

2

b.

0

c.

1

d.

3

 

24.           

V_92_I_5. Se considera matricea de adiacenta alaturata asociata unui graf neorientat cu 7 noduri. Stabiliti prin care dintre metodele urmatoare, graful dat poate deveni arbore.

0 1 0 1 0 0 0

1 0 1 1 1 0 0

0 1 0 1 0 0 1

1 1 1 0 0 0 0

0 1 0 0 0 0 0

0 0 0 0 0 0 0

0 0 1 0 0 0 0

a.

eliminand doua muchii si adaugand o muchie

b.

eliminand o muchie si adaugand o muchie

c.

eliminand doua muchii

d.

adaugand o muchie

 

25.           

V_76_I_7.Se considera arborele cu 8 noduri si muchiile [1,5], [2,3], [3,6], [3,8], [4,6], [5,7], [6,7]. Care dintre nodurile arborelui ar putea fi alese ca radacina pentru ca arborele sa aiba numar maxim de niveluri:

a.

1, 2, 8

b.

3, 4, 7

c.

6

d.

5

 

26.           

V_77_I_5.Care dintre urmatoarele matrice este matricea de adiacenta a unui un graf care are proprietatea ca este arbore?

 

 

a.

b.

c.

d.

27.           

V_70_I_3.Se considera un arbore cu radacina reprezentat in memorie cu ajutorul vectorului de tati : tata = (2,3,0,3,3,2,6,6,4,9).

Stabiliti care dintre nodurile urmatoare sunt extremitatile finale ale unor lanturi elementare de lungime impara care au ca extremitate initiala radacina arborelui.

a.

10 3

b.

3 2 4 5

c.

2 4 5

d.

1 6 9

28.           

V_71_I_1.Precizati cate muchii trebuie inlaturate din graful a carui matrice de adiacenta este data alaturat, astfel incat sa devina arbore?

0 1 1 1 0 0 0

1 0 0 0 1 1 0

1 0 0 1 0 0 1

1 0 1 0 0 0 0

0 1 0 0 0 0 0

0 1 0 0 0 0 1

0 0 1 0 0 1 0

a.

2

b.

1

c.

0

d.

3

29.           

V_19_I_5.Intr-un arbore cu exact 8 noduri radacina, reprezentata de nodul 1, se afla pe nivelul 1 si fiecare nod al arborelui are cel mult 2 descendenti directi. Care este inaltimea minima posibila pentru un astfel de arbore? (Inaltimea unui arbore=numarul maxim de muchii de la radacina la un varf terminal)

a.

4

b.

3

c.

2

d.

1

30.           

V_95_I_2.Cate lanturi elementare de lungime maxima ce leaga doua noduri ale arborelui din figura alaturata exista?

a.

8

b.

6

c.

10

d.

4

31.           

V_7_I_1. Consideram un arbore G cu 7 noduri care are matricea de adiacenta alaturata. Stabiliti care dintre urmatorii vectori este un vector de tati al arborelui dat:

0 1 1 1 0 0 0

1 0 0 0 0 0 0

1 0 0 0 1 0 0

1 0 0 0 0 0 0

0 0 1 0 0 1 1

0 0 0 0 1 0 0

0 0 0 0 1 0 0

a.

(0,1,1,1,3,5,5)

b.

(0,1,3,1,1,5,5)

c.

(0,1,5,5,3,3,5)

d.

(0,1,1,1,5,3,3)

32.           

V_100_I_8. Un arbore cu radacina are n noduri numerotate de la 1 la n. Daca vectorul de tati al acestui arbore (vector notat in continuare cu t) are proprietatea ca

t[i]=i-1 pentru i = 1,2,,n

atunci numarul de noduri care au exact un descendent direct in acest arbore este egal cu:

a.

0

b.

n-1

c.

n

d.

1

33.           

V_10_I_1. Fie arborele G=(V,E) in care multimea varfurilor este V=, iar multimea muchiilor este E=. Considerand varful 1 radacina arborelui, vectorul de tati corespunzator arborelui G este:

a.

T=(0,1,1,3,1,5,3,4,9,4)

b.

T=(0,1,1,1,3,5,3,4,4,4)

c.

T=(0,1,1,1,5,2,4,3,4,9)

d.

T=(0,1,1,1,2,5,3,4,4,9)

34.           

V_31_I_3. Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tati t=(2,5,5,3,0,2,4,6,6). Ascendentii nodului 6 sunt:

a.

1 si 4

b.

2

c.

8 si 9

d.

2 si 5

35.           

V_33_I_6. Intr-un arbore reprezentat prin vectorul de tati t:(8,8,0,3,4,3,4,7), numarul descendentilor nodului 4 este egal cu:

a.

7

b.

2

c.

5

d.

3

36.           

V_34_I_4. Un arbore cu nodurile numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tati (2,5,5,3,0,2,3,7,6), atunci nodurile frunza ale arborelui sunt:

a.

6,7

b.

1,4,8,9