Variante Bac 1-19 N.B.

Varianta 1

2. Câte grafuri neorientate, distincte, cu 4 vârfuri, se pot construi? Două grafuri se consider distincte dacă matricele lor de adiacenţă sunt diferite.

a.24  b. 4   c.4 la puterea 6  d.  2 la puterea 6

Răspuns: d.

2 la puterea n(n-1)/2 = 2 la puterea 4(4-1)/2= 2 la puterea 4*3/2= 2 la puterea 6

Varianta 6

4. Se consideră un graf neorientat G cu 12 noduri si 7 muchii. Care este numărul maxim de componente conexe din care poate fi format graful G?

Răspuns: Maxim 8 componente conexe.

 Varianta 7

3. Se consideră graful neorientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi mulţimea muchiilor {[1,2], [2,3], [3,4], [3,5], [4,5], [1,3], [2,6], [2,4], [4,6]}. Care este numărul minim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să nu mai fie conex?

Răspuns: Se pot elimina minim 2 muchii {[2,6], [4,6]}.

Varianta 8

2. Se consideră un graf neorientat cu 50 noduri şi 32 muchii. Care este numărul maxim de vârfuri cu gradul 0 pe care le poate avea graful?

a. 45 b. 40 c. 41 d. 50

Răspuns: c.

Se deseneaza 10 noduri si se traseaza muchiile.

ð 50-9=41

Varianta 13

3. Scrieţi listele de adiacenţă prin care este reprezentat un graf neorientat conex, cu 6 noduri, numerotate de la 1 la 6, care este eulerian, dar NU este hamiltonian.

              

Varianta 14

1. Se consideră un graf neorientat cu 5 noduri, etichetate cu literele a, b, c, d, e, în care orice nod etichetat cu o vocală este adiacent cu toate nodurile etichetate cu consoane, iar orice nod etichetat cu o consoană este adiacent cu toate nodurile etichetate cu vocale. Câte muchii are acest graf?

a. 12 b. 6   c. 4    d. 3

Răspuns: b.

Acest graf are 6 muchii.

 Varianta 15

4. Se consideră graful neorientat cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,2], [1,6], [1,7], [2,3], [2,6], [3,6], [3,4], [4,5], [4,8], [5,6], [7,8]. Care este gradul minim al unui nod din acest graf? Care sunt nodurile care au acest grad minim?

Răspuns: Se numara si rezulta nodurile cu grad minim: 5, 7, 8.

Varianta 16

1. Dacă n este un număr impar mai mare decât 2, un graf neorientat cu n noduri, în care fiecare nod este adiacent cu exact n-1 noduri, este întotdeauna:

a. arbore

b. graf eulerian

c. graf neconex

d. graf aciclic (graf care nu conţine niciun ciclu)

Răspuns: d.

Deoarece nu exista nici un ciclu.

 Varianta 19

1. Un graf neorientat este complet dacă oricare două noduri distincte ale sale sunt adiacente. Care este numărul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7 noduri, astfel încât graful parţial obţinut să fie arbore?

a. 15 b. 1 c. 6 d. 21

Răspuns: a.

Calculam cu formula n(n-1)/2= 7*6/2= 42/2= 21

      =>21-6 muchii= 15