Problema 4

Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60],[60,20], [2,30] şi [4,30]. Numărul componentelor conexe ale grafului este egal cu:

a. 24 b.26  c . 54 d. 0

Raspuns : b.26

Problema 3

     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 oduri, astfel încât graful parţial obţinut să fie arbore? 
 

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

Raspuns : a.15

Problema 2

 Se consideră un graf neorientat cu 5 noduri, etichetate cu câte o literă distinctă din

mulţimea {a, b, c, d, e}, în care orice nod etichetat cu o vocală este adiacent cu toate

nodurile etichetate cu consoane şi numai cu acestea, iar orice nod etichetat cu o consoană

este adiacent numai cu nodurile etichetate cu vocale. 

Câte muchii are acest graf?  

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

Raspuns : b.6

Problema 1

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 şi care sunt aceste muchii astfel

încât graful parţial obţinut să nu mai fie conex?

Numarul minim de muchii ce pot fi eliminate sunt : 2