Question

Numărul maxim de muchii dintr-un graf neorientat cu 16 noduri și 7 componente conexe este:
Daca ati putea sa-mi si explicati va rog? Dau coroana

Answer 1

Pentru a ajunge la numarul maxim de muchii trebuie sa grupam nodurile astfel incat sa avem numarul maxim de muchii in cat mai putine componente conexe (de preferabil una singura, pe care o facem un "subgraf complet").

Astfel grupam 10 noduri intr-o componenta conexa (facem subgraf complet), ceea ce inseamna ca avem 10*9/2 = 45 muchii.

( Formula pentru numarul de muchii intr-un graf complet cu n noduri : n*(n-1)/2 )

Apoi celelalte 6 noduri reprezinta fiecare cate o componenta conexa. (6 noduri izolate = 6 componente conexe)

In total 16 noduri, 7 componente conexe si 45 de muchii.

Raspuns final : 45 muchii