Yana bir savol. Graph theoryga oid.

Berilgan n ta komputerni bir-biriga qandaydir konfiguratsiyada ulab simli tarmoq hosil qilish kerak.
— Sim bidirectional, ya'ni ikkala tomonga ham ma'lumot jo'natish mumkin.
— A komputerdan B gacha masofa A dan B gacha bo'lgan eng qisqa path uzunligi.

Shartlar:
— Ixtiyoriy ikki komputer orasida ma'lumot almashish mumkin bo'lishi kerak.
— Tarmoq effektiv bo'lishi kerak. Effektivlik bali (tarmoqdagi jami simlar soni) * (ikki komputer orasidagi maksimal masofa) orqali hisoblanadi. Natija qanchalik kichkina bo'lsa tarmoq shuncha effektiv degani.

Eng oddiy yechim: hamma komputerni bir-biri bilan ulash. Jami simlar soni O(n^2), maksimal masofa O(1). Effektivlik: O(n^2).

Yana bitta yechim: komputerlarni halqa shaklida ulash. Simlar soni O(n), maksimal masofa O(n). Effektivlik: O(n^2).

Effektivlik bali O(n^2) dan kichikroq bo'lgan tarmoq dizaynini ishlab chiqa olasizmi?

Formal: Shunday G = (V, E), |V| = n bo'lgan graph topingki, |E| * max(dist(A, B: A, B in V)) < O(n^2) bo'lsin.