Subiecte Bac G.L

Varianta 31: Se considera graful neorientat cu 7 noduri, numerotate de la 1 la 7, si muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre urmatoarele succesiuni de noduri reprezinta un lant care trece o singura data prin toate nodurile grafului? (4p.)

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

b. (4, 5, 3, 6, 7)

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

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

  

Raspuns :  c ,deoarece este singura succesiune de noduri  care trece o singura data prin toate varfurile.

Varianta 32. Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este

reprezentat cu ajutorul matricei de adiacenta alaturate.  Pentru acest graf este adevarata afirmatia: (4p.)

a. Graful este hamiltonian               

b. Graful nu are noduri de grad 0

c. Gradul maxim al unui nod este 3

d. Graful are trei componente conexe

Raspuns:d ,deoarece  graful nu contine toate nodurile conditie necesara pentru un graf hamiltonian, are graduri de nodul 0 iar gradul maxim al unui nod este 4. Dupa cum se poate observa pe desenul corespunzator matricei de adiacenta graful are 3 componente conexe.

Varianta 34. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60], [60,20], [2,30] si [4,30]. Numarul componentelor conexe ale grafului este egal cu:

(4p.)

a. 3

b. 56

c. 54 

d. 0

 Raspuns b. deoarece din 60 de noduri scadem 6 noduri si adaugam 2(cele 2 componente conexe) rezultand 56.

Varianta 35. Un graf neorientat cu 10 noduri, numerotate de la 1 la 10,este reprezentat cu ajutorul listelor de adiacenta alaturate.Câte componente conexe are graful si care este numarul    minim de muchii ce trebuie adaugate pentru ca graful sa fie

conex? (6p.)

1:3,5

2:4

3:1,5

4:2,8

5:1,3

6:

7:10

8:4

9:

10:7

Raspuns :5 componente conexe  ,                                           trebuie adaugate 4  muchii astfel  incat graful sa fie conex.

Varianta 36. Se considera un graf neorientat cu 7 noduri       numerotate de la 1 la 7 si muchiile [1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numarul minim de muchii care trebuie adaugate pentru ca acest graf sa devina eulerian? (4p.)

Raspuns : minim 8 muchii(muchiile albastre) (fiecare nod trebuie sa aiba grad par si trebuie sa existe toate muchiile )

Varianta 38. Urmatorii doi itemi se refera la un graf neorientat cu 7 noduri,nume-rotate 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.)

Raspuns:eliminam [1,5] [5,6] (2 muchii ) si avem 1 si 6 doua componenta conexe   {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: 5 cicluri elementare

Rezolvare :

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

(2,3,4,2)

(3,4,5,2,3)

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

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

Varianta 39. Se considera un graf neorientat cu 8 noduri, numerotate de la 1 la 8, si muchiile [1,5], [1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Daca se elimina nodul 6 si toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?

                                                                                        
 Rezolvare:

Raspuns : 3 componenete conexe