----------------------------------------------------------
Se consideră un graf neorientat cu 50 de noduri și 32 de muchii. Care este numărul maxim de vârfuri cu gradul 0 pe care le poate avea graful?
----------------------------------------------------------
Teorie:
Două vârfuri între care există muchie se numesc adiacente.
Se numește lanț o succesiune de vârfuri L=[x1,x2,⋯xk] cu proprietatea că oricare două vârfuri consecutive sunt adiacente.
Fie G=(X, U) un graf neorientat. Graful G se numește graf complet dacă oricare două vârfuri distincte ale sale sunt adiacente. Un graf complet cu n vârfuri se notează Kn.
Într-un graf complet cu n vârfuri sunt C(2,n)=n∗(n−1)/2 muchii și fiecare vârf are gradul n-1.
Sunt 2^(n∗(n−1)/2) grafuri neorientate distincte cu n vârfuri.
----------------------------------------------------------
n=50,m=32
Calculăm câte noduri nmin sunt necesare pentru a creea un graf complet (sau aproape complet) cu cele m=32 muchii.
nmin*(nmin-1)/2>=32 => nmin*(nmin-1)>=64 => nmin=9
Prin urmare, cu cele 32 de muchii pot uni primele 9 noduri => mai rămân 50-9=41 de noduri izolate (număr maximal)
----------------------------------------------------------
a) 45
b) 40
c) 50
d) 41 (*)
----------------------------------------------------------
Răspuns corect: d)

