Varianta 51
2) Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de
numere pot fi gradele nodurilor grafului?
a) 4, 2, 6, 4, 2 b) 2, 2, 1, 2, 2
c) 1, 1, 1, 1, 1 d) 4, 3, 3, 4, 4
Raspuns:se foloseste formula 2*m=2*9=18,d) este varianta corecta.
4) Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 3 componente conexe?
Raspuns:nr maxim de muchii este 4,existand 6 noduri si 3 componente conexe.
Varianta 52
2) Se consideră graful neorientat din figura alăturată. Care este numărul minim de muchii ce se pot elimina astfel încât graful parţial obţinut să aibă exact 3 componente conexe?
a) 2 b) 4 c)1 d) 3
Raspuns: prin eliminare se obtine graful urmator si rezulta ca trebuie eliminate minim 4 muchii (cele marcate cu rosu), b) fiind varianta corecta.
2) Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 6 noduri,
care nu este conex?
a) 4 b) 15 c)12 d) 10
Raspuns: d
Varianta 57
2) Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat G cu 5 noduri şi 6 muchii?
a) G are cel puţin un ciclu b) G este conex
c) G are gradele tuturor nodurilor numere pare d) G nu poate avea noduri cu gradul 0
Raspuns: a) ,deoarece este pentru orice graf,nu pentru un graf anume,iar toate celelalte variante sunt excluse.
Varianta 58
2) Dacă G este un graf neorientat cu 11 noduri şi 13 muchii, fără noduri cu gradul 0, atunci
numărul maxim de componente conexe pe care le poate avea graful este:
a) 2 b) 4 c) 3 d)5
Raspuns: c)