Variante bac. Subiectul II 61-84 P.D

 Varianta 61:
1.Care este numărul minim de muchii pe care le poate avea graful neorientat G, dacă graful din figura 1 reprezintă un subgraf al lui G, iar graful reprezentat în figura 2 este graf parţial al lui G? (4p.)

         

 a. 8  b. 7  c. 5  d. 6

Raspuns: d. 6 pentru ca in subgraf s-au eliminat nodurile 5 si 6 cu muchiile adiacente cu nodurile respective, iar in graful partial se observa ca s-au eliminate muchiile (2,3) si (1,4) din care obtinem ca 6 e numarul minim de muchii.

Varianta 62:
2. Care dintre următoarele afirmaţii referitoare la graful neorientat G, reprezentat în figura alăturată, este adevărată? (4p.)

a. Graful parţial al lui G obţinut prin eliminarea muchiilor: [5,6], [2,5], [2,3], [2,10],
[10,8], [1,3], este un arbore.
b. Graful conţine un singur ciclu.
c. Cel mai lung lanţ, care conţine numai noduri distincte, are lungimea 8.
d. Numărul nodurilor de grad par este egal cu numărul nodurilor de grad impar.

     
Raspuns : a. (am eliminat muchiile [5,6], [2,5], [2,3], [2,10],[10,8], [1,3] si am desenat ce am obtinut)













Varianta 64:
3.Se consideră un graf neorientat dat prin listele de adiacenţă alăturate. Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful parţial rezultat să fie conex ? (6p.)

1: 2 3
2: 1 3 4
3: 1 2 4 5
4: 2 3 5
5: 3 4

Raspuns: am facut desenul listei de adiacenta si am observat ca se pot elimina maxim 3 muchii. Pot elimina muchiile (1,3), (2,4), (5,3) si de aici rezulta un graf conex.





Varianta 65:
4. Care este numărul minim de muchii care trebuie adăugate grafului alăturat pentru a deveni eulerian?(6p.)





Raspuns: 2 muchii deoarece un graf eulerian trebuie sa continua toate muchiile unui graf. Daca se construiesc de ex muchiile (9,6) si (2,7) se ajunge la un ciclu eulerian.

Varianta 66:
5. Se consideră graful neorientat definit prin mulţimea nodurilor {1,2,3,4,5,6} şi muchiile [1,2],[1,3],[2,3] [6,5],[3,4],[4,5],[4,6]. Care este numărul maxim de muchii care pot fi eliminate din graf pentru a se obţine un graf parţial al său care să fie conex? (4p.)
a. 1 b. 2 c. 0 d. 3

Raspuns: b am desenat graful si am observat ca se pot elimina maxim 2 muchii (1,3) si (6,4).













Varianta 72:
6. Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile: [1,4],[1,8], [2,1], [2,3] [3,1], [4,5], [4,7], [5,7], [6,5]. Scrieţi câte componente conexe are graful dat şi care dintre nodurile acestuia trebuie eliminate astfel încât subgraful obţinut să aibă un număr maxim de componente conexe. (6p.)

Raspuns:  componentele conexe ale grafului dat sunt: {4,5,7} si {1,2,3}; nodurile care trebuie eliminate sunt: 8 si 6.



Varianta 74:
7.Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6 şi următoarele muchii: [1,3] [1,5] [2,3] [2,4] [2,6] [5,3] [6,4].
a) Care este numărul minim de muchii ce trebuie eliminate din acest graf, astfel încât graful parţial obţinut să nu conţină niciun ciclu? (3p.)
b) Care este numărul minim de muchii ce trebuie eliminate din acest graf, astfel încât graful parţial obţinut să aibă exact două componente conexe? (3p.)

Raspuns:   a)  minim 2 muchii.
                     b) 1 muchie (2,3) si rezulta 2 componente conexe {1,3,5} si {2,4,6}.


Varianta 75:
8. Se numeşte graf complet un graf în care oricare două noduri sunt adiacente. Se consideră graful neorientat cu 6 noduri, numerotate de la 1 la 6, definit prin listele de adiacentă alăturate. Câte muchii trebuie adăugate în acest graf astfel încât el să devină graf complet?(4p.)
1: 3 5
2: 3 4 6
3: 1 2 5
4: 2 6
5: 1 3
6: 2 4.

                                               a. 16 b. 14 c. 6 d. 8

Raspuns: d. pentru ca  matricea de adiacenta trebuie sa fie completa,numaram muchiile care adaugate sunt 8.



Varianta 77:
9. Care este numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii? (6p.)

Raspuns: 2 noduri cu gradul 1.


Varianta 78:
10. Care este numărul minim de muchii ale unui graf neorientat conex, cu 100 de noduri? (6p.)

Raspuns:  n-1. 100-1= 99 de muchii.


Varianta 79:
11.  Fie graful neorientat cu 6 noduri, numerotate de la 1 la 6, şi muchiile [1,2], [1,3],[1,4], [2,3], [2,4], [3,4], [3,5], [4,5], [4,6], [5,6]. Care este numărul maxim de muchii care pot fi eliminate astfel încât graful parţial obţinut să-şi păstreze proprietatea de graf hamiltonian? (6p.)

Raspuns: numarul maxim de muchii ce pot fi eliminate incat gradul sa ramana un graf hamiltonian este 3.


Varianta 80:
12.Se consideră un graf neorientat cu 9 noduri, numerotate de la 1 la 9, şi muchiile [1,2],[2,3], [3,7], [4,8], [4,5], [4,6], [5,9], [6,9], [7,8], [6,7], [1,7]. Care este numărul minim de muchii care trebuie adăugate pentru ca graful să devină eulerian? (6p.)

Raspuns: trebuie adaugat minim1 muchie ca graful sa devina eulerian.


Varianta 81:
13.Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4], [3,4], [4,5]}? (4p.)
a. Este graf hamiltonian, dar nu este eulerian. b. Este graf eulerian, dar nu este hamiltonian. c. Este şi graf hamiltonian şi graf eulerian. d. Nu este graf hamiltonian, şi nici nu este graf eulerian.





Raspuns: a. pentru ca graful format reprezinta un cilcu hamiltonian elemtentar care trece prin fiecare nod al grafului.







Varianta 82:
14. Un graf neorientat cu nodurile numerotate de la 1 la 4 este reprezentat prinmatricea de adiacenţă alăturată. Care dintre afirmaţiile de mai jos este adevărată pentru acest graf? (4p.)
a. Graful este arbore b. Graful nu este conex c. Graful este ciclic d. Graful are toate gradele nodurilor numere pare.

Raspuns: a. graful este un arbore, deoarece nodul 1 este radacina, care are ramificatie de dreapta nodul 2 si de stanga nodul 3, adica este arbore pentru ca este conex si fara ciclu si pentru ca are un nod special numit radacina.

Varianta 83:
15.Scrieţi matricea de adiacenţă a unui graf neorientat cu 6 noduri în care toate nodurile au gradul 2 şi care are două componente conexe. (6p.)

Varianta 84:
16. Se consideră graful neorientat cu nodurile numerotate de la 1 la 6 şi având muchiile [1,2], [2,3], [2,5],[2,6], [3,4], [4,5], [4,6], [5,6]. Câte lanţuri , distincte şi de lungime 3 există de la nodul 1 la nodul 4 în graful dat? Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie. (4p.)
a. 2 b. 0 c. 4 d. 3

Raspuns: d. 3, ele sunt : 1-2-3-4, 1-2-6-4, 1-2-5-4.