Question

Matricea de adiacenta a unui graf neorientat cu 7 noduri are 10 elemente nenule. Numarul maxim de componente conexe ale grafului.
+Explicatie rezolvare daca e posibil

Answer 1

Păi din moment ce e graf neorientat și matricea de adiacență are 10 de 1, înseamnă că există 5 muchii. Deci ai un graf cu 7 noduri și 5 muchii.

Tu trebuie să ai cât mai multe componente conexe (care nu-s conectate, componente de sine stătătoare) :))
Bun, ai putea încerca la început să grupezi câte 2 conectate între ele și 1 liber, dar așa o să ai 1-2, 3-4, 5-6 și 7, deci doar 3 muchii.
Dacă ai face câte 3, ar fi:
1- 2   4- 5 și 7    -> aici avem cele 5 muchii, dar numărul de elemente conexe
  \  |        |           -> e trei, să vedem dacă putem face mai mare cu 
    3       6           -> conexiuni de 4

1 - 2   5   6   7
 | \ | 
3 - 4

Aici avem 5 muchii și chiar 4 elemente conexe. 

Am putea merge pe 5 elemente, dar nu avem nevoie de 5, deoarece cu cele 4 am făcut toate muchiile posibile, iar al 5-lea îl putem folosi ca element separat.

Deci răspuns: 4