Question

un graf neorientat are 100 de varfuri si 7 componente conexe numarul maxim de muchii pe care le poate avea acest graf... help ​

Answer 1

Raspuns : 4371 muchii

Formula folosita :

numar de muchii in graf complet cu n noduri = $\frac{n(n-1)}{2}$

Explicatie :

Pentru a avea numarul maxim de muchii :

• 6 componente conexe sunt reprezentate de 6 noduri izolate
• 1 componenta conexa alcatuieste un subgraf complet

Deci 6 noduri izolate si 94 de noduri intr-un subgraf complet.

Un subgraf complet cu 94 de noduri are 94*93/2 = 4371 de muchii.