علی کوچولو در تصورات خود کشوری به نام «اُتوپیا» دارد. کشور او دارای $n$ شهر است٬ منتها بین شهر‌های اتوپیا٬ هیچ راه ارتباطی‌ای وجود ندارد. برای برقراری ارتباط بین این شهر‌ها٬ علی کوچولو می‌خواهد تعدادی جاده بین برخی از شهر‌های کشورش بکشد. ولی از آن‌جایی که او به اصول و فنون راه‌سازی آشنایی ندارد٬ به سراغ کتاب «اصول و فنون راه‌سازی» می‌رود. در این کتاب آمده است:

«اگر می‌خواهید بین $m$ شهر تعدادی جاده‌ی دو طرفه بکشید٬ به طوری که بتوان از هر شهر٬ به هر شهر دیگر رفت٬ باید حداقل $m-۱$ جاده بین این شهرها کشیده شود. دقت کنید هر جاده بین دقیقاً دو شهر کشیده می‌شود و از شهر $A$ می‌توان به شهر $B$ رفت اگر و فقط اگر بتوان با شروع از شهر $A$ و با حرکت روی تعدادی از جاده‌ها به شهر $B$ رسید.»

علی کوچولو برای سروسامان دادن به اوضاع کشور٬ دو هدف زیر را دنبال می‌کند.

۱) بین تعدادی از شهرهای اُتوپیا٬ جاده‌ی دو‌طرفه بکشد به طوری که بتوان از هر شهر آن به هر شهر دیگرش رفت.

۲) تعدادی مرکز پلیس٬ در برخی از شهرهای کشورش (در هر شهر٬ حداکثر یک مرکز پلیس) تأسیس کند. به یک کشور «$d$-حفاظت‌شده» گفته می‌شود٬ اگر برای رفتن از هر مرکز پلیس به یک مرکز پلیس «دیگر» مجبور به طی کردن حداقل $d$ جاده باشیم. قهرمان داستان ما می‌خواهد مراکز پلیس اتوپیا را طوری تأسیس کند که کشورش $d$-حفاظت شده باشد.

بیش‌ترین تعداد مراکز پلیس که باید تأسیس شود (برحسب $n$ و $d$) چقدر باید باشد تا علی کوچولو به دو هدف گفته شده برسد؟ در واقع باید طوری جاده‌ها ساخته و مراکز پلیس تأسیس شوند که به اهداف بالا برسید و بیش‌ترین تعداد مرکز پلیس را داشته باشید.

در هر صورت٬ لازم است گفته‌ی خود را اثبات کنید.

• سوال بعد
• سوال قبل