Matricea de adiacență a unui graf neorientat cu 2020 de noduri are 200 de elemente nenule. Numarul maxim de componente conexe este
a. 2006 b. 2000 c. 1820 d. 400
Va rog cu explicatie!

Răspuns :

Răspuns:

a. 2006

Explicație:

daca ai 200 de elemente nenule inseamna ca ai 100 de muchii. ca sa ai un nr maxim de componente conexe trebuie sa grupezi cat mai multe muchii la un loc. in cazul asta trebuie sa iei 15 noduri si poti sa grupezi maxim 105 muchii (formula n(n-1)/2). cele 15 noduri formeaza o componenta conexa, iar restul de 2005 noduri sunt izolate, adica formeaza 2005 componente conexe. in total ai 2006