चार रंग प्रमेय की व्याख्या
1852 में इंग्लैंड की काउंटियों का नक्शा रंग रहे एक युवा गणितज्ञ ने देखा कि पड़ोसी काउंटियों को अलग रखने के लिए चार रंग काफ़ी लगते हैं। क्या यह हर संभव नक्शे के लिए सच हो सकता है? यह प्रश्न गणित की सबसे प्रसिद्ध समस्याओं में से एक बन गया, इसने एक मशहूर ग़लत प्रमाण को जन्म दिया जो ग्यारह साल तक टिका रहा, और आख़िरकार 1976 में इसे ऐसे तरीक़े से सुलझाया गया जिसने बदल दिया कि गणितज्ञ किसे प्रमाण मानते हैं।
प्रश्न
ऑगस्टस डी मॉर्गन के पूर्व छात्र फ़्रांसिस गुथरी ने पूछा कि क्या किसी भी नक्शे को चार रंगों से इस तरह रंगा जा सकता है कि साझा सीमा वाले देशों को अलग-अलग रंग मिलें। दो नियम प्रश्न को सटीक बनाते हैं। देश जुड़े हुए होने चाहिए, यानी हर देश एक ही टुकड़ा हो, और जो देश केवल एक बिंदु पर मिलते हैं, वे पड़ोसी नहीं गिने जाते। साफ़ है कि तीन रंग हमेशा काफ़ी नहीं होते, क्योंकि आपस में एक-दूसरे को छूने वाले तीन देशों के घेरे से घिरे देश को चौथा रंग चाहिए। प्रश्न यह है कि क्या कभी पाँचवें रंग की ज़रूरत पड़ती है।
ग्राफ़ के रूप में नक्शे
हर देश में एक बिंदु अंकित करें और जब भी दो देशों की सीमा साझा हो, उनके बिंदुओं के बीच एक रेखा खींचें। परिणाम एक ग्राफ़ है, और क्योंकि नक्शा सपाट काग़ज़ पर है, रेखाएँ बिना एक-दूसरे को काटे खींची जा सकती हैं: ग्राफ़ समतलीय है। नक्शे को रंगना इस ग्राफ़ के शीर्षों को इस तरह रंगना है कि हर किनारे के दोनों सिरे अलग-अलग रंग के हों। काम करने वाले रंगों की सबसे छोटी संख्या क्रोमैटिक संख्या कहलाती है, और चार रंग प्रमेय कहता है कि किसी भी समतलीय ग्राफ़ की क्रोमैटिक संख्या चार से अधिक नहीं होती।
केम्पे का असफल प्रमाण
1879 में बैरिस्टर और गणितज्ञ अल्फ़्रेड केम्पे ने एक प्रमाण प्रकाशित किया। इसका चतुर विचार, जिसे अब केम्पे श्रृंखला कहा जाता है, यह है कि जहाँ ज़रूरत हो वहाँ एक रंग ख़ाली करने के लिए देशों की एक जुड़ी हुई श्रृंखला में दो रंगों की अदला-बदली की जाए। यह प्रमाण ग्यारह साल तक स्वीकार किया गया, जब तक 1890 में पर्सी हीवुड ने इसमें एक कमी नहीं ढूँढ ली। हीवुड के सुधार ने एक कमज़ोर परिणाम सिद्ध किया: पाँच रंग हमेशा काफ़ी हैं। केम्पे की श्रृंखलाएँ बची रहीं और अंतिम प्रमाण में एक औज़ार बनीं।
पाँच आसान क्यों है
हर समतलीय ग्राफ़ में एक ऐसा शीर्ष होता है जिसके अधिकतम पाँच पड़ोसी हों; यह ऑयलर के सूत्र से निकलता है, जो n शीर्षों वाले समतलीय ग्राफ़ के किनारों को अधिकतम 3n − 6 तक सीमित करता है। ऐसा एक शीर्ष हटाएँ, उसी तर्क से बाक़ी नक्शे को रंगें, और शीर्ष को वापस रख दें। अगर उसके पड़ोसी पाँच से कम रंग इस्तेमाल करते हैं, तो एक रंग ख़ाली है। अगर वे पाँचों इस्तेमाल करते हैं, तो केम्पे श्रृंखला की एक अदला-बदली हमेशा एक रंग ख़ाली कर देती है। चार रंगों के साथ वही अदला-बदली विफल हो सकती है, और ठीक यही वह कमी है जो केम्पे से छूट गई।
कंप्यूटर प्रमाण
1976 में इलिनॉय विश्वविद्यालय के केनेथ अपेल और वोल्फ़गैंग हाकेन ने यह प्रमेय सिद्ध किया। उन्होंने दिखाया कि हर नक्शे में एक अपरिहार्य समुच्चय के 1,936 विन्यासों में से कम से कम एक होता है, और हर विन्यास न्यूनीकरणीय है: पाँच रंगों की ज़रूरत वाले किसी सबसे छोटे नक्शे में वह नहीं हो सकता। न्यूनीकरणीयता की जाँच में कंप्यूटरों पर एक हज़ार घंटे से ज़्यादा लगे, जो हाथ से पुष्टि करने के लिए बहुत ज़्यादा था। बहुत से गणितज्ञ ऐसे प्रमाण से असहज थे जिसे कोई भी व्यक्ति पूरा नहीं पढ़ सकता था, और कंप्यूटर-सहायता प्राप्त प्रमाणों पर बहस शुरू हो गई।
सरल प्रमाण और पूर्ण सत्यापन
1996 में नील रॉबर्टसन, डैनियल सैंडर्स, पॉल सेमुर और रॉबिन थॉमस ने 633 विन्यासों वाला एक अधिक व्यवस्थित प्रमाण प्रकाशित किया, जिसकी जाँच अब भी कंप्यूटर से होती थी लेकिन जिसकी पुष्टि करना आसान था। 2005 में जॉर्ज गोंथियर और बेंजामिन वर्नर ने पूरे प्रमाण को Coq प्रूफ़ असिस्टेंट में औपचारिक रूप दिया, ताकि एक छोटा, भरोसेमंद प्रोग्राम हर तार्किक क़दम की जाँच करे। आज चार रंग प्रमेय गणित के सबसे अच्छी तरह सत्यापित परिणामों में से एक है।
रंगाई एल्गोरिद्म
किसी दिए गए नक्शे की चार-रंगी रंगाई ढूँढना व्यवहार में तेज़ है, लेकिन किसी सामान्य ग्राफ़ के लिए सबसे कम रंग ढूँढना कठिन है: यह तय करना कि तीन रंग काफ़ी हैं या नहीं, NP-पूर्ण है। व्यावहारिक विधियों में घटती डिग्री के क्रम में ग्रीडी रंगाई, DSATUR, जो अगला सबसे सीमित शीर्ष रंगता है, और बैकट्रैकिंग खोज शामिल हैं, जो विकल्पों को आज़माती है और अटकने पर उन्हें पलट देती है। ग्राफ़ रंगाई से बिना टकराव के परीक्षाओं की समय-सारणी बनती है, रेडियो आवृत्तियाँ इस तरह बाँटी जाती हैं कि पास-पास के ट्रांसमीटर एक-दूसरे में बाधा न डालें, और कंपाइलरों में रजिस्टर आवंटित किए जाते हैं।
ख़ुद आज़माएँ
4 से 120 देशों वाले नक्शे बनाने, उन्हें चार रंगों से हाथ से रंगने और टकरावों को लाल रंग में उभरते देखने के लिए चार रंग नक्शा पेंटर खोलें। ग्रीडी रंगाई, DSATUR या बैकट्रैकिंग को नक्शा क़दम-दर-क़दम हल करने दें, पड़ोसी देशों का ग्राफ़ दिखाएँ, और जाँचें कि नक्शे को वास्तव में कम से कम कितने रंग चाहिए।
अक्सर पूछे जाने वाले प्रश्न
क्या यह प्रमेय नक्शा बनाने वालों की मदद करता है?
शायद ही। असली नक्शे आम तौर पर स्पष्टता के लिए ज़्यादा रंगों से रंगे जाते हैं, और उनमें महासागर, झीलें और कई टुकड़ों वाले देश होते हैं, जिन्हें यह प्रमेय शामिल नहीं करता। इसका महत्व गणितीय है: इसने ग्राफ़ सिद्धांत के विकास को आगे बढ़ाया और यह प्रश्न उठाया कि प्रमाण किसे माना जाए।
केम्पे श्रृंखला क्या है?
दो रंग लें, मान लीजिए लाल और नीला, और लाल रंग का एक देश। उसकी केम्पे श्रृंखला उन सभी लाल और नीले देशों का समुच्चय है, जिन तक आप उससे केवल लाल और नीले पड़ोसियों से होकर पहुँच सकते हैं। पूरी श्रृंखला में लाल और नीले की अदला-बदली करने से रंगाई वैध बनी रहती है, और इससे श्रृंखला के बगल वाले किसी देश के लिए एक रंग ख़ाली हो सकता है।
कई टुकड़ों वाले देश प्रमेय को क्यों तोड़ देते हैं?
अगर कोई देश ऐसे अलग-अलग क्षेत्रों से बना हो सकता है जिन सबका रंग एक ही होना चाहिए, तो पड़ोसी ग्राफ़ समतलीय नहीं रहता, और ऐसे नक्शे बनाए जा सकते हैं जिन्हें प्रति देश दो टुकड़ों के लिए 12 तक कितने भी रंग चाहिए, जैसा हीवुड ने अपनी साम्राज्य समस्या में अध्ययन किया।
पेंटर नक्शे बिंदुओं से क्यों बनाता है?
हर देश वर्ग का वह क्षेत्र है जो किसी एक यादृच्छिक बिंदु के किसी भी अन्य बिंदु से ज़्यादा पास है, यानी एक वोरोनोई आरेख। इससे उत्तल देशों वाले वास्तविक दिखने वाले नक्शे बनते हैं, और दो देश ठीक तभी पड़ोसी होते हैं जब उनके क्षेत्र सीमा का कोई हिस्सा साझा करते हैं, जिसकी गणना ऐप सटीक रूप से करता है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
चार रंग नक्शा पेंटर खोलें