Am o problema, nu-mi trebuie neaparat program, ci explicatie(defapt cred ca exista o formula…)
Problema e din variantele de BAC 2007.
Care este numărul maxim de componente conexe pe care le poate avea un graf neorientat cu 20 noduri şi 12 muchii?
Variante de raspuns : 6, 12, 10, 15
Tind sa cred ca raspunsul corect este 15, dar am nevoie de o explicatie.
Multumesc anticipat.
15 este raspunsul corect.
Intr-un graf cu n noduri avem maxim n * (n – 1) / 2 muchii (graf complet).
Strategia este sa unim cat mai multe muchii intr-o singura componenta conexa, pentru a ramane cat mai multe noduri izolate (fiecare nod izolat avand propria componenta conexa).
1. Din relatia de mai sus, se observa ca putem construi un subgraf complet avand 5 noduri si 10 muchii, facand parte dintr-o componenta conexa. Daca mai conectam inca un nod la 2 dintre nodurile subgrafului respectiv (deci folosind inca 2 muchii), ajungem sa obtinem o componenta conexa avand:
5 + 1 = 6 noduri
10 + 2 = 12 muchii
2. Dupa aceasta operatie ne mai raman disponibile 0 muchii si 20 – 6 = 14 noduri. Deci ne raman 14 noduri izolate, fiecare in propria compomenta conexa. In total avem deci 14 componente conexe + 1 (determinata la punctul 1) = 15 componente conexe.