Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI GRAFOVI

Grafovi: Minimalan broj prijateljstava

Grafovi: Minimalan broj prijateljstava

Postod nkole » Sreda, 01. Avgust 2018, 10:33

Ćao. Nemam pojma kako se radi zadatak, samo sam provalio da su izgleda u pitanju usmereni grafovi.
Na Facebook-u je [inlmath]2000[/inlmath] korisnika i svaki od njih šalje [inlmath]1000[/inlmath] friend request-ova ostalim korisnicima. Dva osobe su prijatelji ukoliko su jedna drugoj poslale friend request. Koliki je najmanji mogući broj prijateljstava na ovoj mreži?
nkole  OFFLINE
 
Postovi: 12
Zahvalio se: 4 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Grafovi: Minimalan broj prijateljstava

Postod Daniel » Sreda, 01. Avgust 2018, 16:12

Haj'mo da vidimo – ako svaki od [inlmath]2000[/inlmath] korisnika šalje po [inlmath]1000[/inlmath] friend requestova, koliko je to onda ukupno friend requestova? Dalje, ako graf ima [inlmath]2000[/inlmath] čvorova (pri čemu svaki čvor predstavlja jednog korisnika), koliko onda u takvom grafu može najviše biti neusmerenih veza (grana)?
Nakon što odgovoriš na ova dva pitanja, rešenje zadatka se sâmo nameće.

Ako se ipak ne snađeš na ovaj način, možeš pokušati i tako što ćeš posmatrati uprošćen slučaj, kod kojeg imaš [inlmath]4[/inlmath] korisnika pri čemu svaki od njih šalje po [inlmath]2[/inlmath] friend requesta, pa zatim isto tako problem od [inlmath]6[/inlmath] korisnika pri čemu svaki od njih šalje po [inlmath]3[/inlmath] friend requesta itd. i da zatim na tako uprošćenim verzijama originalnog problema, uctrtavajući grane u te jednostavne grafove, pokušaš da uočiš princip...
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Grafovi: Minimalan broj prijateljstava

Postod nkole » Sreda, 01. Avgust 2018, 17:29

Hvala na odgovoru. Valjda sam provalio.

Ukupno imamo [inlmath]2\,000\cdot1\,000=2\,000\,000[/inlmath] zahteva, tj. usmerenih grana. Ako konstruišemo graf tako da između svaka dva čvora postoji samo jednosmerna veza, kako bi izbegli stvaranje prijateljstva, on bi imao samo [inlmath]{2\,000\choose2}=\frac{1}{2}2\,000\cdot1\,999=1\,999\,000[/inlmath] veza. Vidimo da grafu fali još [inlmath]1\,000[/inlmath] usmerenih veza, pri čemu sada svaka nova veza znači novo prijateljstvo, pa je odgovor [inlmath]1\,000[/inlmath].
nkole  OFFLINE
 
Postovi: 12
Zahvalio se: 4 puta
Pohvaljen: 1 puta

Re: Grafovi: Minimalan broj prijateljstava

Postod Daniel » Sreda, 01. Avgust 2018, 21:37

Bravo, upravo tako. :thumbup: Nije teško izvesti i za opšti(ji) slučaj, kada imamo [inlmath]2n[/inlmath] korisnika i [inlmath]n[/inlmath] friend requestova. Tada će broj poslatih friend requestova biti [inlmath]2n^2[/inlmath] a ukupan broj jednosmernih veza (u grafu u kojem između svaka dva čvora postoji jednosmerna i samo jednosmerna veza) biće [inlmath]2n\choose2[/inlmath]. Razlika [inlmath]2n^2-{2n\choose2}[/inlmath], kad se sredi, iznosiće [inlmath]n[/inlmath] i to će biti najmanji mogući broj prijateljstava, za koji vidimo da je jednak polovini broja korisnika, odnosno broju poslatih friend requestova po osobi.

Ako „ručno“ izbrojiš dvosmerne veze (prijateljstava) u ovim uprošćenim primerima koje sam ti naveo ([inlmath]n=2[/inlmath], [inlmath]n=3[/inlmath]...), dobićeš kao rezultat upravo vrednost [inlmath]n[/inlmath] za konkretan slučaj.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na GRAFOVI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 0 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 19:59 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs