Question

Care este numărul maxim de componente conexe pe care le poate avea un graf neorientat cu 20 noduri şi 12 muchii?
a.6 , b.12 , c.10, d.15
Nu prea inteleg cum se calculeaza, trebuie sa fac desene pana gasesc cel mai mare numar sau cum?
Va rog ajutati-ma , nu gasesc nici-o formula.

Answer 1

Ideea e in felul urmator: ca sa obtii cat mai multe componente coneze trebuie sa consumi toate muchiile la cat mai putine noduri, adica sa incerci sa obtii cu aproape daca nu cu toate un graf complet.
Un graf complet are n(n-1)/2 muchii
adica n(n-1)=24 cel mai mare n este 5
putem conecta 5 noduri cu 5*4/2=10 muchii si mai raman doua pe care le consumam  adaugand inca un nod pe care il legam cu cele doua muchii de componenta noastra conexa, care are acum 6 noduri
Exista 20 de noduri din care le scadem pe cele 6=14 noduri libere =14 componente conexe
1+14=15 componente