قضیه چهار رنگ
From Wikipedia, the free encyclopedia
قَضیّهٔ چهار رَنگ یا حدس چهار رنگ از مسائل مشهور و قدیمی ریاضیات است که سالها اثباتنشده مانده بود. به بیان ساده (و نادقیق) این قضیه میگوید:
- برای رنگ کردن هر نقشه بهطوریکه کشورها و نواحی همسایه در نقشه همرنگ نباشند فقط چهار رنگ کافی است.
سه رنگ برای نقشههای سادهتر کافیست ولی یک رنگ چهارم اضافی برای برخی نقشهها لازم است. مثل نقشههایی که در آنها یک ناحیه با تعداد فرد نواحی دیگر احاطه شدهاست که به یکدیگر در یک دایره وصل هستند. قضیه ۵ رنگ که اثباتی کوتاه و ابتدایی دارد، بیان میکند که ۵ رنگ برای رنگ آمیزی نقشه کافیست . این قضیه در اواخر قرن ۱۹ اثبات شدهاست (هیووو ۱۸۹۰). اثبات اینکه ۴ رنگ کافیست بسیار سخت تر است. تعدادی اثباتهای غلط و مثالهای نقض از زمان ارائه قضیه ۴ رنگ در ۱۸۵۲ بیان شدهاند.
این مسئله به صورت معادله ابتدا درسال۱۸۵۲ عنوان شد و سرانجام در سال ۱۹۷۶ با کمک رایانه توسط کی اپپل و و. هیکن حل شد. این اولین قضیه مهمی بود که با استفاده از کامپیوتر به اثبات رسید. آنها نشان دادند که مجموعهای از ۱۹۳۶ نقشه وجود دارد که هیچکدام از آنها نمیتوانند قسمتی از یکی از کوچکترین مثال نقضهای قضیه چهار رنگ باشند. اپل و هیکن از یک برنامه کامپیوتری خاص منظوره استفاده کردند تا ثابت کنند هیچکدام از این نقشهها از این قاعده مستثنا نیستند. علاوه بر این هر نقشهای فارغ از این که مثال نقض هست یا نه، حتماً قسمتی را شامل میشود که شبیه یکی از آن ۱۹۳۶ نقشه میباشد و اثبات این نیاز به صدها صفحه تحلیل دست نویس بود. اپل و هیکن نتیجه گرفتند که اگر بخواهد کوچکترین مثال نقضی وجود داشته باشد باید شامل یکی از آن ۱۹۳۶ نقشه باشد. این تناقض به این معنی بود که هیچ مثال نقضی وجود ندارد و قضیه درست میباشد. در ابتدا اثبات آنها از طرف همه ریاضیدانها مورد تأیید واقع نشد، چرا که چک کردن یک اثبات کامپیوتری توسط انسان امکانپذیر نبود (Swart ۱۹۸۰).