در کشور عجایب تعدادی شهر٬ که یکی از آن‌ها پایتخت است٬ و تعدادی جاده وجود دارد که هر جاده دو شهر را به‌هم وصل می‌کند. می‌دانیم از هر شهر به پایتخت مسیری (شامل چند جاده و شهر میانی) وجود دارد. به زیرمجموعه‌ای از جاده‌ها یک «نقشه» می‌گوییم اگر دو شرط زیر را داشته باشد:

الف) با این مجموعه از جاده‌ها از هر شهری مسیری به پایتخت موجود باشد.

ب) با حذف هریک از این جاده‌ها شرط «الف» دیگر برقرار نباشد.

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

یک نقشه «قابل ساخت» است اگر در بین همه‌ی نقشه‌ها کم‌ترین هزینه را داشته باشد. (ممکن است بیش از یک نقشه‌‌ی قابل‌ساخت داشته باشیم.)

ثابت کنید نقشه‌ی قابل ساختی وجود دارد که بین هیچ‌کدام از شهرهای تنهای آن جاده‌ای (از بین جاده‌های نقشه یا سایر جاده‌ها ) وجود ندارد.

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