
قضیهٔ چهار رنگ: با فقط چهار مداد، هر نقشهٔ مسطحی را رنگ کن!
هدفهای این ایستگاه#
- قضیهٔ چهار رنگ و شرطهایش (نقشهٔ مسطح، همسایگی با مرز مشترک) را دقیق بیان کنی.
- نقشه را به گراف تبدیل کنی و با راهبرد «فرمانروا اول» و برگشت از بنبست رنگ کنی.
- کمترین تعداد رنگ (عدد رنگی) چند گراف کوچک را پیدا کنی و کاربردهای رنگآمیزی را توضیح دهی.
- گزارش کتبی تایپشده بنویسی و در ارائهٔ ۴ تا ۶ دقیقهای راهبردت را روایت کنی.
مأموریت تو: نقشهکش حرفهای شو
- هدف
- گزارش کتبی تایپشده بنویسی و در ارائهٔ ۴ تا ۶ دقیقهای راهبردت را روایت کنی.
- نمای کلی
- یکی از سناریوها را برگزین (نقشهٔ استانهای ایران، باغوحش دستکم ۱۰ محوطهای، یا فستیوال با چند صحنه)، نقشه را به گراف تبدیل کن، با حداکثر ۴ رنگ و یک راهبرد روشن رنگ کن، بسنج که ۳ رنگ کافی است یا نه، و همه را در گزارش کتبی تایپشده و ارائهٔ ۴ تا ۶ دقیقهای بیاور.
بخش ۱: ماجرا: معمایی که ۱۲۴ سال طول کشید#
سال ۱۸۵۲ فرانسیس گاتری هنگام رنگ کردن نقشهٔ شهرستانهای انگلستان پرسید: «آیا ۴ رنگ همیشه کافی است تا هیچ دو همسایهای همرنگ نباشند؟» سه رنگ همیشه کافی نیست؛ پنج رنگ همیشه کافی است (این را راحتتر میشود ثابت کرد). اما چهار؟ بیش از یک قرن «اثباتهای» غلط آمد و رفت تا سال ۱۹۷۶کِتِنَالپِ و ولفگانگ هاکن با کمک رایانه، که حدود ۱۲۰۰ ساعت محاسبه کرد، آن را ثابت کردند: اولین قضیهٔ بزرگ ریاضی که با کمک رایانه ثابت شد. (رایانه هم احتمااً لبعدش یک چای حسابی خورد!)
بخش ۲: مرز مشترک، نه نقطه#
دو ناحیه فقط وقتی همسایهاند که یک خط مرزی مشترک داشته باشند؛ تماس در یک نقطه (مثل خانههای قطری شطرنج) حساب نیست.
بخش ۳: نقشهٔ مسطح#
روی کاغذ صاف (یا کره). روی سطحهای دیگر مثل «چنبره» (شکل دونات) ممکن است تا ۷ رنگ لازم شود.

بخش ۴: هر کشور یک تکه#
اگر کشوری چند تکهٔ جدا داشته باشد و همهٔ تکهها باید همرنگ باشند، ممکن است ۴ رنگ کافی نباشد؛ قضیه برای ناحیههای یکتکه است.
بخش ۵: جعبهابزار : ۲ از نقشه تا گراف#
هر کشور را یک «گره» و هر مرز مشترک را یک «یال» بکش. حالا رنگ کردن نقشه یعنی رنگ کردن گرهها طوری که دو سر هیچ یالی همرنگ نباشند. گراف نقشهها همیشه «مسطح» است (میشود آن را بدون تقاطع یالها کشید). به کمترین تعداد رنگ لازم برای یک گراف «عدد رنگی» میگویند. قضیهٔ چهار رنگ یعنی: عدد رنگی هر گراف مسطح حداکثر ۴ است.

بخش ۶: جعبهابزار : ۳ راهبرد رنگآمیزی#
- فرمانروا را پیدا کن: کشوری که بیشترین همسایه را دارد.
- آن را با رنگ اول (مثاً لقرمز) رنگ کن؛ هیچ همسایهاش دیگر قرمز نمیشود.
- کشورهای بعدی را به ترتیب (پرهمسایهترها اول) رنگ کن و هر بار «اولین رنگ مجاز» فهرستت را بزن.
- اگر به بنبست رسیدی، نترس: یک قدم به عقب برگرد، رنگ یک کشور قبلی را عوض کن و ادامه بده (به این «عقبگرد» میگویند).
- در پایان همهٔ مرزها را یکییکی بازبینی کن.
بخش ۷: عدد رنگی سه گراف#
دور ۵ تایی (۵ کشور حلقهوار): با ۲ رنگ نمیشود، چون رنگها باید یکیدرمیان باشند و ۵ فرد است؛ پس ۳ رنگ لازم و کافی است. چهار کشوری که هر کدام با هر سه کشور دیگر همسایه است: هر ۴ باید رنگ متفاوت داشته باشند؛ پس ۴ رنگ. «چرخ ۵ پره» (یک کشور وسط که دور ۵ تایی را محاصره کرده): دور به ۳ رنگ نیاز دارد و وسطی با همه همسایه است؛ پس ۴ رنگ. پس حتی نقشههای کوچک هم ممکن است واقعً۴ رنگ بخواهند.

بخش ۸: برنامهٔ امتحان#
شش درس: ریاضی، فیزیک، شیمی، زیست، ادبیات و زبان. اگر دو درس دانشجوی مشترک داشته باشند، با یک یال وصلشان میکنیم: ریاضی–فیزیک، ریاضی–شیمی، فیزیک–شیمی، شیمی–زیست، زیست–ادبیات، ادبیات–زبان، زبان–ریاضی و فیزیک–زیست. ریاضی، فیزیک و شیمی هر سه به هم وصل اند؛ پس دستکم ۳ نوبت لازم است. یک رنگآمیزی با ۳ نوبت: نوبت ۱ ریاضی و زیست، نوبت ۲ فیزیک و ادبیات، نوبت ۳ شیمی و زبان. پس ۳ نوبت امتحان کافی است.


بخش ۹: فرکانس دکلها#
دو دکل نزدیک نباید فرکانس یکسان داشته باشند؛ دکل = گره، نزدیکی = یال، فرکانس = رنگ. (این گرافها همیشه مسطح نیستند؛ پس گاهی بیش از ۴ فرکانس لازم است.)
بخش ۱۰: زمانبندی#
امتحانها، جلسهها یا صحنههای یک فستیوال: تداخل = یال، بازهٔ زمانی = رنگ.
بخش ۱۱: طراحی تراشه و حافظه#
در کامپایلرها به متغیرهایی که همزمان لازم اند «ثبات» جدا داده میشود؛ این هم رنگآمیزی گراف است.

بخش ۱۲: مراحل انجام پروژه#
- یک سناریو برگزین: نقشهٔ استانهای ایران، باغوحش (دستکم ۱۰ محوطه، ۴ تیم نگهبان = ۴ رنگ) یا فستیوال (صحنهها، ۴ بازهٔ زمانی = ۴ رنگ).
- نقشه را خوانا بکش یا تهیه کن و قاعدهٔ همسایگی را بنویس.
- نقشه را به گراف تبدیل کن و تعداد همسایههای هر ناحیه را بشمار.
- با راهبرد فرمانروا اول و عقبگرد، با حداکثر ۴ رنگ رنگ کن.
- بسنج: ۳ رنگ کافی بود؟ اگر نه، کدام بخش (مثاً لیک دور فرد با یک همسایهٔ مشترک) رنگ چهارم را لازم کرد؟
- گزارش کتبی تایپشده بنویس و ارائه را آماده کن.


بخش ۱۳: ساختار ارائهٔ ۴ تا ۶ دقیقهای#
مقدمه (حدود ۱ دقیقه): داستان معمای ۱۲۴ ساله. قضیه (حدود ۱ دقیقه): همسایگی و شرطهای مهم. راهبرد تو (حدود ۲ دقیقه): از کجا شروع کردی، کجا به بنبست خوردی و چطور برگشتی. کاربرد و نتیجه (حدود ۱ تا ۲ دقیقه): یک کاربرد واقعی و آموختههایت. تمرین سریع: نقشهٔ ۶ کشوری خودت را بکش که حتمً۴ رنگ لازم داشته باشد. نقشهٔ رنگشده، گراف و پاسخ پرسشهای تحلیل را در گزارش کتبی تایپشده بیاور. گزارش را به تسهیلگر سرپرست بده و ارائه را با نقشهٔ بزرگ یا اسلاید اجرا کن.
خودآزمایی#
گزینهٔ درست را انتخاب کن و «بررسی پاسخها» را بزن.
نمایش پاسخنامه
۱. دو ناحیه که یک خط مرزی مشترک دارند؛ ۲. ۳؛ ۳. در ۱۹۷۶ با کمک رایانه به دست اپل و هاکن
پرسشهای مرور و کاربرد#
- قضیهٔ چهار رنگ را با شرطهایش به زبان خودت بگو.
- فرمانروای نقشهات کدام بود و آیا از آن شروع کردی؟
- آیا ۳ رنگ کافی بود؟ اگر نه، کجا و چرا رنگ چهارم لازم شد؟
- رنگآمیزی گراف را در کدام بخش دیگر زندگی میبینی؟
مهر گذرنامه: پیش از رفتن به ایستگاه بعد#
پیش از رفتن به ایستگاه بعدی، این موارد را علامت بزن:
آفرین! یک مهر دیگر در گذرنامهٔ ریاضیات خورد.