Matricea de adiacență a unui graf neorientat cu 100 de noduri are 9900 de elemente nule. Indicați numărul maxim de componente conexe ale grafului.
a. 50 b. 90 c. 1000 d. 9800
Răspunsuri la întrebare
Răspuns de
5
Matrice de adiacenta are 9900 elemente nenule = 4950 muchii
Numarul de muchii ale unui graf complet cu 100 de noduri = 100*99/2 = 4950 muchii.
Rezulta ca graful e complet, ceea ce inseamna o singura componenta conexa.
Te rog verifica daca ai scris corect datele problemei. Variantele date de tine nu sunt posibile.
theodoracheru:
Variantele sunt scrise corect. Nu cred ca a dat un rezultat din variante pentru ca in enunt spune "9900 de elemente nule", iar rezolvarea pe care ai facut-o este facuta in cazul in care cele 9900 de elemente sunt nenule.
Exista vreo conditie daca elementele sunt nule?
greșeala mea, nu am citit bine enunțul.9900 elemente nule înseamnă 100 de elemente nenule. (matricea are dimensiunea 100*100). asta înseamnă 50 de muchii
pentru a avea numărul maxim de componente conexe trebuie sa "grupăm" toate muchiile într-o singură componentă.
la o sută de muchii avem nevoie de minim 10 noduri (un graf complet cu 9 noduri având 45 de muchii, iar unul cu 10 avand 55)
iar restul de noduri libere formează propria componenta conexă
**la 50 de muchii avem nevoie de minim 11 noduri (un graf complet cu 10 noduri având 45 de muchii, unul cu 11 noduri având 55). aceste 11 noduri formează o componentă iar restul 89 sunt noduri izolate (fiecare fiind o componentă conexa). deci 89+1=90 de componente conexe
răspuns B
Multumesc mult de tot pentru raspuns! ^.^
Alte întrebări interesante
Limba română,
8 ani în urmă
Limba română,
8 ani în urmă
Limba română,
8 ani în urmă
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Engleza,
9 ani în urmă