قضیه چهاررنگ

مثالی از یک "نقشه" چهاررنگ

نقشه آمريكا، رنگ شده با چهار رنگ،‌ بدون در نظر گرفتن آب ها و كشور هاي ديگر.

قَضیّهٔ چهاررَنگ یا حدس چهاررنگ از مسائل مشهور و قدیمی ریاضیات است که سال‌ها اثبات نشده مانده بود. به بیان ساده (و نادقیق) این قضیه می‌گوید:

برای رنگ کردن هر نقشه به طوری که کشورها و نواحی همسایه در نقشه هم‌رنگ نباشند فقط چهار رنگ کافی است.

سه رنگ برای نقشه های ساده تر کافیست ولی یک رنگ چهارم اضافی برای برخی نقشه ها لازم است. مثل نقشه هایی که در آن ها یک ناحیه با تعداد فرد نواحی دیگر احاطه شده است که به یکدیگر در یک دایره وصل هستند. قضیه 5 رنگ که اثباتی کوتاه و ابتدایی دارد، بیان می کند که 5 رنگ برای رنگ آمیزی نقشه کافیست . این قصیه در اواخر قرن 19 اثبات شده است(هیووو 1890). اثبات اینکه 4 رنگ کافیست بسیار سخت تر است. تعدادی اثبات های غلط و مثال های نقض از زمان ارائه قضیه 4 رنگ در 1852 بیان شده اند.

این مسئله به صورت معادله ابتدا درسال۱۸۵۲ عنوان شد و سرانجام در سال ۱۹۷۶ با کمک رایانه توسط کی اپپل و و. هیکن حل شد. این اولین قضیه مهمی بود که با استفاده از کامپیوتر به اثبات رسید. آنها نشان دادند كه مجموعه اي از 1936 نقشه وجود دارد كه هيچ كدام از آنها نمي توانند قسمتي از يكي از كوچكترين مثال نقض هاي قضيه چهار رنگ باشند. اپل و هيكن از يك برنامه كامپيوتري خاص منظوره استفاده كردند تا ثابت كنند هيچ كدام از اين نقشه ها از اين قاعده مستثنا نيستند. علاوه بر اين هر نقشه اي فارغ از اين كه مثال نقض هست يا نه، حتما قسمتي را شامل مي شود كه شبيه يكي از آن 1936 نقشه مي باشد و اثبات اين نياز به صدها صفحه تحليل دست نويس بود. اپل و هيكن نتيجه گرفتند كه اگر بخواهد كوچكترين مثال نقضي وجود داشته باشد بايد شامل يكي از آن 1936 نقشه باشد. اين تناقض به اين معني بود كه هيچ مثال نقضي وجود ندارد و قضيه درست مي باشد. در ابتدا اثبات آنها از طرف همه رياضيدان ها مورد تاييد واقع نشد، چرا كه چك كردن يك اثبات كامپيوتري توسط انسان امكان پذير نبود(Swart 1980).

قاعده سازي دقيق قضيه

بيان شهودي قضيه چهار رنگ، يعني:"در هر افرازي از يك صفحه، كه نقشه ناميده مي شود، هر ناحيه مي تواند به طوري رنگ شود كه هيج دو ناحيه مجاوري هم رنگ نباشند و در اين رنگ آميزي از بيشتر از چهار رنگ استفاده نشود"، نيازمند تفسير و درك مناسب و درستي است. براي مثال هر ناحيه نقشه بايد پيوسته باشد. در دنياي واقعي، همه كشورها پيوسته نيستند(براي مثال ايالت آلاسكا در آمريكا و نخجوان در آذربايجان). به علت يكپارچه نبودن قلمرو بعضي كشور ها ممكن است چهار رنگ كافي نباشد.

نمونه اي از نقشه كشور جمهوری آذربایجان با نواحي غير پيوسته.

يك بيان ساده تر اين قضيه به كمك تئوري گراف مي باشد. مي توان مجموعه نواحي يك نقشه را به يك گراف بدون جهت نظير كرد كه هر راس يك ناحيه و هر يال دو راس هاي دو ناحيه كه مجاور هستند را به هم متصل مي كند. گراف حاصل مسطح مي باشد: يعني اين گراف را مي توان در صفحه نقشه قرار داد و هر راس را در جاي دلخواهي از ناحيه متناظر آن گذاشت، بدون آنكه هيچ دو يالي همديگر را قطع كنند. به بيان گرافي،‌ قضيه چهار رنگ بيان مي كند كه رئوس يك گراف مسطح را مي توان با چهار رنگ رنگ آميزي كرد به طوري كه هيچ دو راس مجاور همرنگ نباشند.(Thomas 1998, p. 849; Wilson 2002)

تاريخچه

تلاش هاي اوليه براي اثبات

conjecture اولين بار در سال 1852 مطرح شد. در آن هنگام فرانسيس گاتري مشغول رنگ آميزي نقشه انگلستان بود كه متوجه شد چهار رنگ براي اين كار كافيست. فرانسيس اين موضوع را با برادرش فردريك مطرح كرد، كه بعدا وي آن را به پيش د مرگان برد. اولين منبع منتشر شده از آرتور كيلي مي باشد(آرتور كيلي 1879).

تلاش هاي ناموفق بسياري براي اثبات اين قضيه انجام شده است. اثبات آلفرد كمپه در سال 1879 كه بسيار مورد قبول واقع شد و اثبات ديگري كه پيتر گاتري تيت در 1880 مطرح كرد، همگي از اين دست بودند. هر دوي اين اثبات هاي اشتباه 11 سال بعد از مطرح شدنشان به ترتيب توسط پرسي هيوود و ژوليوس پترسن نقض شدند.

اثبات توسط كامپيوتر

در دهه هاي 60 و 70 ميلادي هاينريش هيش، رياضيدان آلماني، روش هاي اثبات به كمك كامپيوتر را توسعه داد. متاسفانه در اين زمان وي به وي فرصت استفاده از ابررايانه داده نشد تا كارش را ادامه دهد. ولي ديگران روش هاي او را ادامه دادند. در سال 1976،‌ در حالي كه گروه هايي از رياضيدانان در رقابت براي بدست آوردن اثبات كامل بودند،‌ كنس اپل و وولفانگ هيكن در دانشگاه Illinois اعلام كردند كه قضيه را اثبات كرده اند. آنها در يك سري كارهاي الگوريتمي توسط John A. Koch همياري شده بودند (Wilson 2002).

اگر حدس چهار رنگ نادرست بود، حداقل يك نقشه وجود داشت با كمترين تعداد نواحي ممكن، كه به پنج رنگ نياز داشت. اثبات نشان داد كه چنين كوچكترين مثال نقضي نمي تواند وجود داشته باشد؛ از طريق دو مفهوم فني(Wilson 2002; Appel & Haken 1989; Thomas 1998, pp. 852–853):

• مجموعي اجتناب ناپذير دربر دارنده ي نواحي اي مي باشد كه هر نقشه حداقل بايد يكي از آنها را دارا باشد.
• يك آرايش كاهش پذير وضعيتي از كشورهاست كه نمي توانند در يك مثال نقض كمينه اتفاق بيفتند. اگر در يك نقشه يك آرايش كاهش پذير وجود داشته باشد، نقشه مي تواند به يك تقشه كوچكتر كاهش يابد. حال اگر اين نقشه كوچكتر بتواند با چهار رنگ رنگ آميزي شود،‌ نقشه اصلي هم مي تواند با چهار رنگ رنگ آميزي شود. اين به اين معني است كه اگر نقشه اصلي نتواند با چهار رنگ رنگ شود نقشه كوچكتر هم نمي تواند، پس نقشه اصلي كمينه نيست.

با استفاده از قوانين و روش هاي رياضي بر پايه ي خواص آرايش هاي كاهش پذير، اپل و هيكن يك مجموعه اجتناب ناپذير از آرايش هاي كاهش پذير يافتند كه نشان مي دهد هيچ مثال نقض كمينه اي وجود ندارد. اثبات آنها تعداد بينهايت نقشه ممكن را به 1936 آرايش كاهش پذير(كه بعدا به 1476 رسيد) كاهش داد. پروسه چك كردن اين تعداد حالت با كامپيوتر بيشتر از هزار ساعت به طول انجاميد(Appel & Haken 1989).

ساده سازي و بازبيني

الگوريتم هايي كه براي اثبات قضيه استفاده شدند داري پيچيدگي زماني (O(n² مي باشد كه n تعداد راس ها است. در سال 2005 Benjamin Werner و George Gonthier به كمك ‍‍‍‍‍Coq‍‍ براي اثبات قضيه قاعدي سازي كردند. اين كار نياز به اعتماد به برنامه هاي كامپيوتري كه براي درستي سنجي حالت هاي خاص بودند را از بين برد. حال تنها نياز است به Coq kernel اعتماد شود(Gonthier 2008).

خلاصه ي ايده ي اثبات

اين قسمت خلاصه اي است بر مبناي مقدمه كتاب Every Planar Map is Four Colorable نوشته ي اپل و هيكن. با وجود اينكه اثبات اوليه كمپه اشتباه بود، ابزار پايه اي براي اثبات قضيه را ساخت. اظهارات كمپه بدين صورت بود: اگر نواحي مسطحي كه با گراف جدا شده اند مثلث نباشند، به عبارت ديگر دقيقا سه گوشه در مرزهايشان نداشته باشند، مي توانيم به آنها بدون معرفي رئوس، يال اضافه كنيم تا مثلثي شوند. اگر اين گراف مثلثي قابل رنگ شدن با 4 رنگ يا كمتر باشد گراف اصلي هم قابل رنگ شدن است چرا كه همان نحوه ي رنگ شدن در صورت از بين بردن يال ها مجاز است.

منابع

• Allaire, F. (1997), "Another proof of the four colour theorem—Part I", Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer. 20: 3–72 
• Appel, Kenneth; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490 
• Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567 
• Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map Problem", Scientific American 237 (4): 108–121, doi:10.1038/scientificamerican1077-108 
• Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Providence, RI: American Mathematical Society, ISBN 0-8218-5103-9 
• Bernhart, Frank R. (1977), "A digest of the four color theorem.", Journal of Graph Theory 1: 207–225, doi:10.1002/jgt.3190010305 
• Cayley, Arthur (1879), "On the colourings of maps", Proc. Royal Geographical Society (Blackwell Publishing) 1 (4): 259–261, doi:10.2307/1799998, JSTOR 1799998 

• Fritsch, Rudolf; Fritsch, Gerda (1998), The Four Color Theorem: History, Topological Foundations and Idea of Proof, New York: Springer, ISBN 978-0-387-98497-1 
• Gonthier, Georges (2008), "Formal Proof—The Four-Color Theorem", Notices of the American Mathematical Society 55 (11): 1382–1393, http://www.ams.org/notices/200811/tx081101382p.pdf 
• Gonthier, Georges (2005), A computer-checked proof of the four colour theorem, unpublished, http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf 
• Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143 
• Heawood, P. J. (1890), "Map-Colour Theorem", Quarterly Journal of Mathematics, Oxford 24: 332–338 
• Magnant, C.; Martin, D. M. (2011), "Coloring rectangular blocks in 3-space", Discussiones Mathematicae Graph Theory 31 (1): 161–170, http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=plik&nIdA=21787&sTyp=HTML&nIdSesji=-1 
• Nash-Williams, C. St. J. A. (1967), "Infinite graphs—a survey", J. Combinatorial Theory 3: 286–301, MR0214501 .
• O'Connor; Robertson (1996), The Four Colour Theorem, MacTutor archive, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html 
• Pegg, A.; Melendez, J.; Berenguer, R.; Sendra, J. R.; Hernandez; Del Pino, J. (2002), "Book Review: The Colossal Book of Mathematics", Notices of the American Mathematical Society 49 (9): 1084–1086, Bibcode 2002ITED...49.1084A, doi:10.1109/TED.2002.1003756, http://www.ams.org/notices/200209/rev-pegg.pdf 
• Reed, Bruce; Allwright, David (2008), "Painting the office", Mathematics-in-Industry Case Studies 1: 1–8, http://www.micsjournal.ca/index.php/mics/article/view/5 
• Ringel, G.; Youngs, J.W.T. (1968), "Solution of the Heawood Map-Coloring Problem", Proc. Nat. Acad. Sci. USA 60 (2): 438–445, doi:10.1073/pnas.60.2.438, PMC 225066, PMID 16591648 
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1996), "Efficiently four-coloring planar graphs", Efficiently four-coloring planar graphs, STOC'96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM Press, pp. 571–575, doi:10.1145/237814.238005 
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), "The Four-Colour Theorem", J. Combin. Theory Ser. B 70 (1): 2–44, doi:10.1006/jctb.1997.1750 
• Saaty, Thomas; Kainen, Paul (1986), "The Four Color Problem: Assaults and Conquest", Science (New York: Dover Publications) 202 (4366): 424, Bibcode 1978Sci...202..424S, doi:10.1126/science.202.4366.424, ISBN 0-486-65092-8 
• Swart, ER (1980), "The philosophical implications of the four-color problem", American Mathematical Monthly (Mathematical Association of America) 87 (9): 697–702, doi:10.2307/2321855, JSTOR 2321855, http://mathdl.maa.org/images/upload_library/22/Ford/Swart697-707.pdf 
• Thomas, Robin (1998), "An Update on the Four-Color Theorem", Notices of the American Mathematical Society 45 (7): 848–859, http://www.ams.org/notices/199807/thomas.pdf 
• Thomas, Robin (1995), The Four Color Theorem, http://people.math.gatech.edu/~thomas/FC/fourcolor.html 
• Thomas, Robin, Recent Excluded Minor Theorems for Graphs, p. 14, http://people.math.gatech.edu/~thomas/PAP/bcc.pdf 
• Wilson, Robin (2002), Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8 

در ویکی‌انبار پرونده‌هایی دربارهٔ قضیه چهاررنگ موجود است.