Jump to content
Forum Roportal
Sign in to follow this  
HellCritical

Problema BAC INFO Pascal

Rate this topic

Recommended Posts

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

Raspunsul este d. 15. Poate sa-mi explice cineva de ce?!

 

 

 

Poate cineva sa-mi explice notiunea de arbore si de graf? In Pascal... Am incercat sa caut informatii pe google, dar nu inteleg nimic... Sunt singurele lucruri pe care nu le stiu. Si dau bacul la informatica. Stiu absolut tot inafara de asta... Am citit de aici:http://www.scribd.com/doc/22557393/Arbori-si-Grafuri . Si nu am inteles nimic...

Share this post


Link to post
Share on other sites

In link-ul pus de tine nu ai toate definitiile necesare pentru problema pusa.

 

Citeste aici:

http://www.scribd.com/doc/96771804/Introducere-grafuri

gasesti definitia unei componente conexe la pagina 10.

 

Daca din ce citesti in materialele astea nu ai inteles nimic .... cred ca singura solutie e sa iti cauti un profesor de meditatii.

Share this post


Link to post
Share on other sites

invata neaparat grafuri pt ca sunt de baza la info. din ce am vazut eu la teste(cand am dat eu) peste 90% aveau subiecte de grafuri. nu stiu daca mai ai timp sa inveti, capitolul e f mare.

 

La problema ta: (citeste rezolvarea dupa ce inveti grafurile)

 

o componenta conexa = graf in care pt oricare 2 varfuri ai un lanț intre ele. comp conexa este si nodul fara vecini(sau nod izolat care are gradul 0).

 

Tu ai 12 muchii. Aceste muchii trebuie sa le pui pe toate pe cat mai putine noduri si sa ramana cat mai multe noduri izolate(ca sa ai cat mai multe comp. conexe pt ca asta cere problema).

 

Pe n noduri poti pune maxim n(n-1)/2 muchii. Acesta e un rezultat din teoria grafurilor. Sper sa dai peste el cand inveti.

 

cum tu ai 12 muchii ai de rezolvat: n(n-1)/2 = 12. si rezulta 6 deoarece iei nr de noduri imediat superior care poate contine 12 muchii. 5 noduri nu se poate dc acestea pot avea maxim 10 muchii.

 

deci ai o componenta conexa de 6 noduri. Acum mai raman restul de 14 noduri care formeaza fiecare o comp. conexa. Deci, in total 15 comp. conexe.

  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×