MATEMANIJA

Ć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?

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

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

Bravo, upravo tako. 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.