Variante Bac 51-59 P.B

                                                          Varianta 51

2) Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de

numere pot fi gradele nodurilor grafului?

a) 4, 2, 6, 4, 2                  b) 2, 2, 1, 2, 2

c) 1, 1, 1, 1, 1                  d) 4, 3, 3, 4, 4

                                          


Raspuns:se foloseste formula 2*m=2*9=18,d) este varianta corecta.

  

 4) Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3 componente conexe?    

Raspuns:nr maxim de muchii este 4,existand 6 noduri si 3 componente conexe.

                                
Varianta 52 

 2) Se consideră graful neorientat din figura alăturată. Care este numărul minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă exact 3 componente conexe?

a) 2                      b) 4                    c)1                 d) 3            

Raspuns:  prin eliminare se obtine graful urmator si rezulta ca trebuie eliminate minim 4 muchii (cele marcate cu rosu), b) fiind  varianta corecta.

 Varianta 56

2)   Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri,

care nu este conex?

a) 4         b) 15        c)12           d) 10

  






Raspuns: d

             

                                          Varianta 57

2) Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri  şi 6 muchii?

a) G are cel puţin un ciclu                                           b) G este conex

c) G are gradele tuturor nodurilor numere  pare         d) G nu poate avea noduri cu gradul 0

 Raspuns: a) ,deoarece este pentru orice graf,nu pentru un graf anume,iar toate celelalte variante sunt excluse.

                                              Varianta 58

2) Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci

numărul maxim de componente conexe pe care le poate avea graful este:

a) 2         b) 4          c) 3        d)5

 Raspuns: c)

Variante bac G.L

 

 

Varianta 33  . Se considera graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenta alaturate. Care dintre multimile urmatoare de noduri are toate elementele extremitati ale unor lanturi de lungime 2 cu cealalta extremitate în nodul 5? (4p.)

 

1: 4,5,6

2: 5

3: 4

4: 1,3

5: 1,2,6

6: 1,5

a. {1,4,6} b. {2} c. {3}  d. {2,6}

Raspuns : d ,sunt  singurele care lanturi de lungime 2 cu cealalta extremitate in nodul 5.

Varianta 35 . Se considera graful neorientat cu multimea nodurilor {1,2,3,4,5,6,7,8} si multimea muchiilor {[1,2], [2,3], [2,4], [4,7], [2,6], [1,5], [5,6], [6,8], [7,8]}.

 Pentru a trasforma graful într-un arbore, putem elimina: (4p.)

   a. muchiile [1,5] si [1,2]              

   b. muchia [5,6]

   c. nodul 3                             

   d. muchiile [2,6] si [4,7]

Raspuns:d.deoarece daca eliminam muchiile  [1,5] si [1,2] sau nodul 3  graful nu este conex,iar daca eliminam muchia    [5,6]    graful nu este aciclic .      

Varianta 36  . Câte muchii trebuie eliminate dintr-un graf neorientat complet cu 20 de noduri, pentru ca acesta sa devina arbore? Un graf este complet daca oricare doua noduri distincte sunt adiacente.

Rezolvare (2 la puterea 190 ) - 19

Varianta 38 . Urmatorul doi itemi se refera la un graf neorientat cu 7 noduri, numerotate de la 1 la 7 si muchiile

[1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].

1. Care este numarul minim de muchii care trebuie eliminate astfel încât graful sa aiba 3 componente conexe? (6p.)

Eliminam [1,5] [5,6] (2 muchii ) si avem 1 componenta conexa 6 componenta conexa  iar  {2,3,4,5,7} formeaza a treia componenata conexa .

2. Câte cicluri elementare distincte exista în graf? Doua cicluri sunt distincte daca difera prin cel putin o muchie.

Raspuns: 7 cicluri elementare

Varianta 41. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenta alaturata, au gradul un numar par? (4p.)

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. 1 b. 3 c. 2 d. 5

Rezolvare :suma de pe prima coloana este nr par rezulta ca nodul 1 are grad par.

Varianta 42. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de

adiacenta alaturata, au gradul 0? (4p.)

0 0 0 1 1

0 0 0 0 0

0 0 0 0 0

1 0 0 0 0

1 0 0 0 0

a. 2 b. 1 c. 3 d. 0

REZ:coloanele 2 si 3 au doar zero(acestea nu sunt incidente cu nici un  nod)  deci au gradul zero.

Varianta 43. Un graf neorientat este reprezentat prin matricea de adiacenta alaturata. Câte grafuri partiale distincte, formate doar din noduri cu gradul egal cu 2, se pot obtine din graful dat? Doua grafuri sunt distincte daca matricele lor de adiacenta difera. (4p.)

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. 2 b. 1 c. 3 d. 0

Raspuns :b

Rezolvare 

0 1 0 0 1

1 0 0 1 0

0 0 0 1 1

0 1 1 0 0

1 0 1 0 0

Varianta 45. Graful neorientat G este dat prin matricea de adiacenta alaturata. Câte vârfuri ale grafului G au gradul 1? (4p.)

0 0 0 0 1

0 0 1 1 0

0 1 0 1 1

0 1 1 0 1

1 0 1 1 0

a. 1 b. 2 c. 3 d. 0

R:a ,fiindca doar prima coloana are suma egala cu 1

Variante Bac 22-29 N.B.

Varianta 22

4. Într-un graf neorientat cu 10 noduri, numerotate de la 1 la 10, există câte o muchie între oricare două noduri numerotate cu numere consecutive şi câte o muchie între nodul numerotat cu 10 şi fiecare dintre celelalte noduri. Câte subgrafuri cu exact 3 noduri, toate

adiacente două câte două, are graful dat?

Răspuns: Subgrafuri 1,2,10; 2,3,10; 3,4,10; 4,5,10; 5,6,10; 6,7,10; 7,8,10; 8,9,10.

=>8 subgrafuri

Varianta 25

2. Un graf neorientat cu 8 noduri are gradele nodurilor egale cu 1,2,4,2,3,2,1,x. Pentru ce valoare a lui x graful este arbore?

a. x=1         b. x<3        c. x>3         d. nicio valoare

Răspuns: a.

Notam x=8 si observam ca este sufficient ca x sa ia o valoare pentru a fi arbore.

Varianta 26

1. Pentru graful neorientat din figura alăturată, care este numărul de

muchii ale celui mai lung lanţ, format din noduri distincte, ce are ca extremităţi nodurile 1 şi 3?

a. 2    b. 3   c. 1    d. 4

Răspuns: d.

De la 1 mergem prin cele mai multe noduri pana ajungem la 3.

1,2,4,5,3.

Varianta 29

1. Care este numărul maxim de noduri de grad 3 într-un graf neorientat cu 5 noduri?

a. 4    b. 5   c. 3    d. 2

Răspuns: a.

Nodurile de grad 3 sunt: 1, 2, 4, 5.

=>4 noduri