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