Variante Bac. P.B

                                                           Varianta 82.

2) Un graf neorientat cu nodurile numerotate de la 1 la 4 este reprezentat prin

matricea de adiacenţă alăturată. Care dintre afirmaţiile de mai jos este

adevărată pentru acest graf?

                                                           

a. Graful este arbore                    b. Graful nu este conex

c. Graful este ciclic                      d. Graful are toate gradele nodurilor numere pare

Raspuns: a,deoarece este aciclic,conex si contine noduri cu grad par,de aici reiese ca graful este arbore.

                                                            Varianta 83.

3) 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. 

Raspuns:  0 1 1 0 0 0                                                  

                  1 0 1 0 0 0

                  1 1 0 0 0 0

                  0 0 0 0 1 1

                  0 0 0 1 0 1  
Am desenat graful neorientat  cu cele doua componente conexe si am scris matricea de adiacenta corespunzatoare.
                       
                                                                  Varianta 84.

1) 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.

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

Raspuns: a) .Lantul 1-2-6-4  si 1-2-5-4.

                                                                   Varianta 91.

1) Se consideră un graf neorientat G cu 101 noduri şi 101 muchii. Numărul maxim de vârfuri  izolate ale grafului poate fi:

a) 0                   b)  10                  c) 50          d) 86

Raspuns: a) pentru ca intre 2 noduri nu pot fi mai mult de o muchie.

                                                                  Varianta 93.

1)      Care este numărul minim de noduri ce trebuie eliminate din graful alăturat astfel încât graful parţial obţinut să nu fie conex?

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

Raspuns : d),deoarece orice muchie este eliminata ,rezulta 2 componente conexe.

                                                             Varianta 94.

1) Care dintre nodurile grafului neorientat cu 5 noduri, numerotate

de la 1 la 5, dat prin matricea de adiacenţă alăturată, are gradul cel mai mare?

0 1 1 0 0

1 0 1 0 1

1 1 0 1 1

0 0 1 0 1

0 1 1 1 0

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

Raspuns: b) ,deoarece nodul 1 are gradul 2,nodul 2 are gradul 3,nodul 4 are gradul 2 iar nodul 5 are gradul 3 =>3 are gradul 4,cel mai mare.

                                                                        Varianta 97.

1) Se consideră un graf neorientat 5 noduri şi 3 muchii. Care este numărul maxim de noduri  cu grad 1 care pot exista în graf?

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

Raspuns: c)  si anume nodurile 1,2,4 si 5 iar nodul 3 are gradul 2.

                                                                       Varianta 99   

                                          

1)      Considerăm un graf neorientat cu 5 noduri şi 3 muchii format din două componente conexe. Ştiind că doar patru dintre noduri au gradul 1, scrieţi matricea de adiacenţă a grafului.

Graful cu 2 componente conexe                       Raspuns:                 Matricea de adiacenta