देश
सीमाएँ
प्रयुक्त रंग
टकराव

चार रंग प्रमेय के बारे में अधिक

चार रंग प्रमेय नक्शा पेंटर

नक्शा कितना भी जटिल हो, उसे इस तरह रंगने के लिए चार रंग हमेशा काफ़ी होते हैं कि साझा सीमा वाले देशों का रंग कभी एक न हो। यह कथन इतना सरल है कि कोई बच्चा क्रेयॉन से इसे परख सकता है, फिर भी इसे सिद्ध करने में एक सदी से ज़्यादा समय और एक कंप्यूटर लगा। एक यादृच्छिक नक्शा ख़ुद रंगें, देखें कि कौन-सी सीमाएँ टकराती हैं, और फिर तीन विधियों को यह काम करते देखें: एक तेज़ ग्रीडी नियम से, जिसे कभी-कभी पाँचवाँ रंग चाहिए, लेकर एक बैकट्रैकिंग खोज तक, जो हमेशा चार रंगों से काम चला लेती है। एक रंग चुनें और देशों पर क्लिक करके उन्हें रंगें; जब दो पड़ोसियों का रंग एक जैसा होता है, तो उनके बीच की सीमा लाल हो जाती है। जो देश केवल एक कोने पर मिलते हैं, उनका रंग एक जैसा हो सकता है। या यह काम कंप्यूटर पर छोड़ दें: एक विधि चुनें और उसे काम करते देखने के लिए हल करें दबाएँ, या एक-एक चाल देखने के लिए क़दम दबाएँ। सबसे कम रंग जाँचता है कि क्या यह नक्शा तीन या दो रंगों से भी काम चला सकता है। नया नक्शा दूसरा नक्शा बनाता है, और पड़ोसी दिखाएँ साझा सीमा वाले देशों का नेटवर्क बनाता है।

यह कैसे काम करता है

  1. देशों की संख्या चुनें और नया नक्शा दबाएँ, या दिखाए गए नक्शे से शुरू करें।
  2. एक रंग चुनें और देशों पर क्लिक करके उन्हें रंगें, और उन लाल सीमाओं पर नज़र रखें जहाँ पड़ोसी टकराते हैं।
  3. एक विधि चुनें और उसे नक्शा रंगते देखने के लिए हल करें या क़दम दबाएँ, और यह देखने के लिए कि इस नक्शे को कितने रंग चाहिए, सबसे कम रंग दबाएँ।

नक्शों से ग्राफ़ तक

हर देश में एक बिंदु रखें और जिन दो देशों की सीमा साझा है, उनके बिंदुओं को जोड़ दें। नक्शा एक ग्राफ़ बन जाता है, और नक्शे को रंगना बिंदुओं को इस तरह रंगने जैसा ही है कि जुड़े हुए बिंदु अलग-अलग रंग के हों। क्योंकि नक्शे सपाट काग़ज़ पर बनाए जाते हैं, ये ग्राफ़ समतलीय होते हैं: इन्हें बिना रेखाओं को एक-दूसरे से काटे बनाया जा सकता है। जो देश केवल एक बिंदु पर मिलते हैं, जैसे किसी कोने पर चार वर्ग, वे पड़ोसी नहीं हैं। चार रंग प्रमेय कहता है कि हर समतलीय ग्राफ़ को चार रंगों से रंगा जा सकता है। मौजूदा नक्शे का ग्राफ़ देखने के लिए पड़ोसी दिखाएँ चालू करें।

रंगने के तीन तरीक़े

ग्रीडी रंगाई देशों को एक-एक करके लेती है, सबसे ज़्यादा पड़ोसियों वाले देशों से शुरू करके, और हर देश को वह पहला रंग देती है जिसे उसके पड़ोसियों ने इस्तेमाल नहीं किया है। यह तेज़ है लेकिन दूरदर्शी नहीं, और कुछ नक्शों पर इसे पाँचवें या छठे रंग तक का सहारा लेना पड़ता है। 1979 में डैनियल ब्रेलाज़ द्वारा आविष्कृत DSATUR हमेशा अगला वह देश चुनता है जिसके पड़ोसियों में पहले से सबसे ज़्यादा अलग-अलग रंग हों, जिससे आम तौर पर वह जाल टल जाता है। बैकट्रैकिंग बारी-बारी से रंग आज़माती है और जब किसी देश के लिए कोई रंग नहीं बचता, तो अपने सबसे हाल के चुनाव पलटकर फिर से कोशिश करती है; यह हमेशा चार रंगों वाली रंगाई ढूँढ लेती है, कभी-कभी कई बार पीछे लौटने के बाद।

अक्सर पूछे जाने वाले प्रश्न

चार रंग हमेशा काफ़ी क्यों होते हैं?

किसी को अब तक कोई छोटा कारण नहीं मिला है। 1976 में केनेथ अपेल और वोल्फ़गैंग हाकेन के प्रमाण ने दिखाया कि हर नक्शे में 1,936 छोटे विन्यासों में से कोई एक होना ज़रूरी है, और इनमें से हर एक को हटाकर बाद में रंगाई बहाल की जा सकती है; इन सबकी जाँच में एक हज़ार घंटे से ज़्यादा कंप्यूटर समय लगा। 1996 में नील रॉबर्टसन, डैनियल सैंडर्स, पॉल सेमुर और रॉबिन थॉमस के एक सरल कंप्यूटर प्रमाण को 633 विन्यासों की ज़रूरत है, और 2005 में जॉर्ज गोंथियर ने Coq प्रूफ़ असिस्टेंट से एक प्रमाण की पूरी तरह पुष्टि की।

क्या कुछ नक्शों को चारों रंग चाहिए?

हाँ। ऐसे चार देश जिनमें से हर एक बाक़ी तीनों को छूता हो, जैसे एक देश जो तीन अन्य देशों के घेरे से घिरा हो, उन्हें चार रंग चाहिए। फिर भी बहुत से नक्शे तीन से काम चला लेते हैं, और सबसे कम रंग स्क्रीन पर दिख रहे नक्शे के लिए यह पता लगाता है। सामान्य रूप से यह तय करना कि किसी नक्शे को तीन रंगों से रंगा जा सकता है या नहीं, एक कठिन, NP-पूर्ण समस्या है, भले ही चार रंग हमेशा काफ़ी हों।

ग्रीडी विधि कभी-कभी पाँच रंग क्यों इस्तेमाल करती है?

यह हर देश को एक बार रंगती है और कभी अपना फ़ैसला नहीं बदलती। कोई शुरुआती चुनाव बाद वाले किसी देश को चारों रंगों से घिरा छोड़ सकता है, और तब बचने का एकमात्र रास्ता पाँचवाँ रंग होता है। इसके बजाय बैकट्रैकिंग पीछे जाकर पहले के चुनाव बदल देती।

क्या यह प्रमेय दूसरी सतहों पर भी सही है?

गोले पर, हाँ: यह समतल जैसा ही है। टोरस पर, यानी डोनट की सतह पर, कुछ नक्शों को सात रंग चाहिए, और सात रंग हमेशा काफ़ी हैं, जैसा पर्सी हीवुड ने दिखाया। अगर देश कई अलग-अलग टुकड़ों से बने हो सकते हैं, जैसे उपनिवेशों वाला कोई राष्ट्र, तो चार रंग काफ़ी नहीं रहते।

क्या कुछ सर्वर पर भेजा जाता है?

नहीं। नक्शा, रंगने की विधियाँ और जाँच आपके ब्राउज़र में चलती हैं। आपकी सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ