Problema BAC INFO Pascal

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...

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.

Incep sa inteleg din asta pe care mi l-ai dat tu! Este mai ok!

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.