Un graf neorientat complet are 21 de noduri. Indicați numărul de muchii ce pot fi eliminate, astfel în
graful parțial obținut să fie conex și fără cicluri.
a. 211
b. 209
C. 190
d. 188
Răspunsuri la întrebare
Răspuns de
7
Modelul publicat astazi ?
Ideea e in felul urmator :
Un graf complet cu n noduri are n*(n-1)/2 muchii (in cazul nostru 21*20/2 = 210 muchii)
Un graf conex fara cicluri are n-1 muchii (in cazul nostru 20 muchii)
Deci trebuie sa eliminam 210-20 = 190 muchii
RASPUNS FINAL :
C. 190
halloyay:
Da, e modelul de azi.Multumesc mult de explicatie, nu stiam ca un graf conex fara cicluri are formula aia. Tu dai bacul tot la informatica?
Da, tot la info.
Ai cumva o foaie cu formula pt grafuri? ca n am reusit sa imi incropesc niciuna
Nu am avut nevoie până acum de foaie cu formule, deobicei fac un exemplu mai mic cu 3-4 noduri și încerc să induc o formula.
Dar cred că în curând o să îmi trebuiască și mie o foaie cu formule pentru grafurile mai "speciale"
Adica cele hamiltoniene si euleriene?
Daca o sa iti termini foaia aceea, te rog nu uita de mine:))
Alte întrebări interesante
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Chimie,
8 ani în urmă
Matematică,
8 ani în urmă
Engleza,
9 ani în urmă
Matematică,
9 ani în urmă