--------------------------------------------------------------------------
Precizați care sunt numărul maxim și numărul minim de componente conexe pentru un graf neorientat cu 200 noduri şi 101 muchii? 
--------------------------------------------------------------------------
Teorie:
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.
--------------------------------------------------------------------------
Noduri n = 200, Muchii m = 101...
La n=200 avem in GRAF COMPLET => m = [n(n-1)/2] = 19.900 muchii
--------------------------------------------------------------------------
Dar noi avem doar m = 101 muchii...
Prin urmare, daca ne raportam doar la muchii... gasind un n maximal (nmax). Gasim nmax, pentru care nmax*(nmax-1)/2 <= m = 101.
Raportadu-ne la muchii, pentru cazul nostru, avem un graf complet cu nmax = 14 noduri: 14*13/2 = 7*13 = 91 muchii.
Completam graful complet (Componenta conexa - 1) cu muchiile ramase, respectiv m-nmax*(nmax-1)/2 = 10 muchii, asta insemnand ca putem adauga DOAR un sigur nod.
Astfel, pentru Componenta conexa - 1 avem nmax = nmax+1 = 15 noduri. Acest graf este Componenta conexa - 1.
Mai raman n-nmax = 185 componente conexe (noduri care nu sunt legate prin muchii intre ele).
--------------------------------------------------------------------------
Concluzia 1: NUMAR MAXIMAL DE COMPONENTE CONEXE: n-nmax+1 = 185+1 = 186.
Concluzia 2: NUMAR MINIMAL DE COMPONENTE CONEXE: nmin = n-m = 200-101 = 99.
--------------------------------------------------------------------------
a) 187 si 97
b) 186 si 98
c) 187 si 99
d) 186 si 99 (*)
--------------------------------------------------------------------------
Răspuns corect: d)

