سوال ۳۱

در نقشه‌ی مسئله‌ی ‎۳۰ حداکثر تعداد شهرهایی را که بین هیچ دوتایی از آن‌ها جاده‌ی مستقیم وجود ندارد با ‎$b$‎ و حداقل تعداد مراکز کنترل ترافیک را با ‎$a$‎ نشان می‌دهیم.

آیا می‌توان نقشه‌ای رسم کرد که در آن ‎$a+b$‎ از تعداد شهرها بیش‌تر باشد؟

پاسخ

شهرها را به دسته $A$ و $B$ تقسیم می‌کنیم. $B$ شامل شهرهایی است که بین هیچ دوتایی از آن‌ها جاده مستقیم وجود ندارد و تعداد آن‌ها حداکثر ممکن را دارد معلووماست که تعدد این شهرها برابر با $b$ می‌باشد. اگر بخواهیم تعداد مراکز کنترل ترافیک حداقل باشد کافی است به تمام شهر‌های دسته‌ی $A$ مرکز کنترل ترافیک اختصاص دهیم. ضمنا لازم نیست به هیچ کدام از اعضای مجموعه‌ی $B$ مرکزی اختصاص دهیم زیرا هر کداماز آن‌ها حداقل به یکی از اعضای مجموعه‌ی $A$ مستقیما جاده دارند( چون در غیر این صورت عضوی از $A$ که به هیچ کدام از اعضای $B$ جاده نداشته باشد باید جز مجموعه‌ی $B$ قرار می‌گرفت). پس تعداد اعضای $A$ حداکثر برابر با $a$ می‌باشد. پس ‎$a+b$ از تعداد شهر‌ها بیش‌تر نیست.