----------------------------------------------------------
Un graf neorientat are 20 de noduri și 9 muchii. Indicați numărul maxim de componente conexe din care poate fi format 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.
Un graf neorientat se numește graf conex dacă pentru oricare două vârfuri x și y diferite ale sale, există cel puțin un lanț care le leagă, adică x este extremitatea inițială și y este extremitatea finală.
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=20,m=9
Calculăm câte noduri nmin sunt necesare pentru a creea un graf complet (sau aproape complet) cu cele m=9 muchii.
nmin*(nmin-1)/2>=9 => nmin*(nmin-1)>=18 => nmin=5
Prin urmare, primele 5 noduri formează prima componentă conexă => mai rămân (componente conexe distincte) 20-5=15
Total componente conexe maxime: 15+1 = 16
(Vezi <1-4.png> de pe site mdcoroiu.ro)
----------------------------------------------------------
a) 14
b) 15
c) 16 (*)
d) 17
----------------------------------------------------------
Răspuns corect: c)

