--------------------------------------------------------------------------
Graful G are matricea de adiacență alăturată. Câte grafuri parțiale conexe distincte și diferite de G se pot obține din el. Două grafuri parțiale sunt distincte dacă diferă prin cel puțin o muchie.
--------------------------------------------------------------------------
Teorie:
Un graf se numește graf conex dacă între oricare două noduri există cel puțin un lanț.
Un graf se numește parțial al unui alt graf, dacă este format din aceeași mulțime de noduri și o submulțime a muchiilor.
Dacă un graf neorientat cu n noduri și m muchii este conex, numărul maxim de muchii care se pot elimina pentru a obține un graf parțial conex este: m-n+1.
--------------------------------------------------------------------------
Matricea:
0 1 0 0 0 
1 0 1 1 0 
0 1 0 1 1 
0 1 1 0 1 
0 0 1 1 0
Avem:
n=5, m=6
Putem elimina maxim: m-n+1=6-5+1=2 muchii pentru a obține un graf partial conex.
Putem elimina muchiile: (2,3),(3,4),(3,5),(4,5),(2,4),[(2,3),(3,4)],[(2,3),(3,5)],[(2,3),(4,5)],[(3,4),(3,5)],[(3,4),(4,5)],[(3,4),(2,4)],[(3,5),(2,4)] sau [(4,5),(2,4)].
Adică vom putea obține un total de 13 grafuri parțiale conexe distincte.
(Vezi <1-3.png> de pe site mdcoroiu.ro)
--------------------------------------------------------------------------
a) 16
b) 5
c) 13 (*)
d) 8
--------------------------------------------------------------------------
Răspuns corect: c)

