Question

Care este numărul minim de noduri pe care îl poate conţine un
graf neorientat cu 50 de muchii, şi în care 15 noduri sunt izolate?

Answer 1

Deci in primul rand numărul minim de noduri pe care îl poate conţine un

graf neorientat cu 50 de muchii

Numarul minim de noduri se realizeaza cand graful e complet. Un graf complet are n(n-1)/2 muchii, unde n = nr noduri

n(n-1)/2 = 50

n(n-1) = 100

n^2 - n - 100 = 0

Adica n ~= 10 virgula ceva. Ne trebuie un numar intreg mai mare decat valoarea exacta, deci n =11

11 noduri necesare pentru muchii + 15 noduri izolate = 26 noduri