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