--------------------------------------------------------------------------
Dacă G este un graf neorientat cu 11 noduri și 13 muchii, fără noduri cu gradul 0, atunci numărul maxim de componente conexe pe care le poate avea graful este:
--------------------------------------------------------------------------
Teorie:
Definiție. Se numește COMPONENTĂ CONEXĂ a grafului G=(X,U) un subgraf G1=(X1,U1) conex, al lui G care are proprietatea că nu există niciun lanț în G care să lege un vârf din X1 cu un vârf din X-X1.
Definiție. Se numește LANȚ în G succesiunea de vârfuri L=[xi1,xi2,...,xik], cu proprietatea că oricare două vârfuri consecutive din L sunt adiacente, adică [xi1,xi2], [xi2,xi3], ..., [xik-1,xik]U. Vârfurile xi1 și xik se numesc extremitățile lanțului, iar numărul de muchii care apar în L se numește lungimea lanțului L.
--------------------------------------------------------------------------
Presupunem că F este Kn, deci ca F să fie complet avem n(n-1) muchii.
Verificăm câte noduri are un graf cu 13 muchii.
n(n-1)<13 => n^2-n-13<0
delta=1+52=53, radical(53)(aprox)=7,...
n1,2=(1+/-7)/2=>n=4
Pentru n=4 avem 12 muchii ca graful F să fie complet. =>
- 1 componentă conexă {1,2,3,4,5}
- 6,7,8,9,10,11 - fiecare nod e izolat (6 componente conexe)
=> total 7 componente conexe (maxim)
Dar, problema precizează fără noduri de gradul 0.
Luăm muchii din F și unim cele 6 noduri și le unim două câte două.
Prin urmare:
- 1 componentă conexă {1,2,3,4,5}
- 1 componentă conexă {6,7}
- 1 componentă conexă {8,9}
- 1 componentă conexă {10,11}
TOTAL> 4 componente conexe maxim
--------------------------------------------------------------------------
a) 2
b) 4 (*)
c) 3
d) 5
--------------------------------------------------------------------------
Răspuns corect: b)

