Earth–Moon problem
पृथ्वी-चंद्रमा समस्या गणित में ग्राफ रंग पर एक अनसुलझी समस्या है। यह समतल मानचित्र रंग समस्या का एक विस्तार है (चार रंग प्रमेय द्वारा हल किया गया), और 1959 में गेरहार्ड रिंगेल द्वारा प्रस्तुत किया गया था। गणितीय शब्दों में, यह द्वि-समतलीय आलेखों की वर्णात्मक संख्या की तलाश करता है। यह ज्ञात है कि यह संख्या कम से कम 9 और अधिकतम 12 है। सूत्रीकरण मानचित्र रंग समस्या में, यूक्लिडियन तल में बस जुड़े क्षेत्रों का एक संग्रह या एक स्थलवैज्ञानिक रूप से समकक्ष स्थान, जैसे कि पृथ्वी की सतह पर देश, को रंगीन किया जाना है ताकि, जब दो क्षेत्रों की सीमा की लंबाई गैर-शून्य हो, तो उनके अलग-अलग रंग हों। प्रत्येक क्षेत्र के लिए एक शीर्ष और प्रत्येक दो पड़ोसी क्षेत्रों के लिए एक किनारा बनाकर इसे एक ग्राफ रंग समस्या में बदला जा सकता है, जिससे एक समतल ग्राफ का उत्पादन होता है जिसके शीर्ष रंगीन होते हैं। चार रंग प्रमेय के अनुसार, अधिकतम चार अलग-अलग रंगों का उपयोग करके ऐसा करना हमेशा संभव है, चाहे कितने भी क्षेत्र दिए गए हों। इसके बजाय, पृथ्वी-चंद्रमा समस्या में, पृथ्वी पर प्रत्येक देश की चंद्रमा की सतह पर एक संबंधित कॉलोनी है, जिसे एक ही रंग दिया जाना चाहिए। इन उपनिवेशों की सीमाएँ हो सकती हैं जो पृथ्वी पर सीमाओं की व्यवस्था से पूरी तरह से अलग हैं। प्रत्येक देश और उसके उपनिवेश के लिए एक ही रंग का उपयोग करते हुए देशों को रंगीन होना चाहिए, ताकि जब दो देश पृथ्वी पर या चंद्रमा पर एक सीमा साझा करें तो उन्हें अलग-अलग रंग दिए जाएं। रिंगेल की समस्या यह पूछती हैः यह सुनिश्चित करने के लिए कितने रंगों की आवश्यकता है कि सभी देश रंगीन हो सकते हैं, चाहे उनकी सीमाएँ कैसे भी व्यवस्थित हों? एक बार फिर, किसी भी देश और उसके उपनिवेश के प्रत्येक जोड़े के लिए एक शीर्ष के साथ, और देशों या उपनिवेशों के बीच प्रत्येक निकटता के लिए एक किनारे के साथ, ग्राफ सिद्धांत में एक के बराबर एक ही प्रश्न को वाक्यांश कर सकते हैं। समस्या के इस संस्करण में जिन आलेखों का परिणाम होता है, वे द्वि-समतलीय आलेखों हैं, या समान रूप से मोटाई दो के आलेखों के समानः उनके किनारों को दो उपसमुच्चय (पृथ्वी की निकटता और चंद्रमा की निकटता) में विभाजित किया जा सकता है जैसे कि संबंधित दो उप-आलेखों दोनों समतल हैं। गणितीय शब्दों में, रिंगेल की समस्या द्वि-समतलीय आलेखों की अधिकतम वर्णात्मक संख्या के लिए पूछती है। सीमाएँ शीर्षों पर एक द्वि-समतलीय ग्राफ के अधिकांश किनारे होते हैं (एक समतलीय ग्राफ की संख्या से दोगुना), जिससे यह पता चलता है कि इसमें केवल 11 पड़ोसियों के साथ कम से कम एक शीर्ष होता है। इस शीर्ष को हटाना, शेष ग्राफ को बार-बार रंगना, और फिर हटाए गए शीर्ष के लिए सबसे छोटे-संख्या वाले अप्रयुक्त रंग का उपयोग करने से अधिकतम 12 रंगों के साथ रंग बनता है; यह ग्राफ के अपक्षय क्रम के लिए लालची रंग है। इसलिए, द्वि-समतलीय ग्राफ के लिए अधिकतम 12 रंगों की आवश्यकता होती है। 9 रंगों की आवश्यकता वाले द्वि-समतलीय ग्राफ का एक उदाहरण 6-वर्टेक्स पूर्ण ग्राफ और 5-वर्टेक्स चक्र ग्राफ के जुड़ाव के रूप में बनाया जा सकता है। इसका मतलब है कि ये दोनों उपग्राफ एक उपग्राफ से दूसरे तक सभी संभावित किनारों से जुड़े हुए हैं। परिणामी ग्राफ में 11 शीर्ष हैं, और पूर्ण उपग्राफ के लिए 6 रंगों और चक्र उपग्राफ के लिए 3 रंगों की आवश्यकता होती है, जो कुल मिलाकर 9 रंग देते हैं। 1974 में थॉम सुलांके द्वारा किए गए इस निर्माण ने रिंगेल के इस अनुमान को गलत साबित कर दिया कि 8 रंग हमेशा पर्याप्त होंगे। इसके बाद, द्वि-समतलीय 9-महत्वपूर्ण ग्राफ (न्यूनतम ग्राफ जिनके लिए नौ रंगों की आवश्यकता होती है) के असीम रूप से कई उदाहरणों का निर्माण किया गया है। समस्या पर आगे की प्रगति की कमी के बावजूद, 2018 में एलेन गेथनर ने अनुमान लगाया कि इस समस्या के लिए रंगों की सही संख्या 11 है। वह 10-वर्णात्मक द्वि-समतल ग्राफ के लिए कई उम्मीदवारों का सुझाव देती है, जिसमें एक गुट के साथ एक चक्र ग्राफ के मजबूत उत्पाद के रूप में प्राप्त ग्राफ और किसी भी शीर्ष को हटाकर प्राप्त ग्राफ शामिल है। इन ग्राफों को 10 रंगों की आवश्यकता के लिए दिखाया जा सकता है, क्योंकि उनके पास इतना बड़ा कोई स्वतंत्र सेट नहीं है कि कम रंगों वाले रंग में सबसे बड़ा रंग वर्ग हो। इसके अतिरिक्त, वे एक द्वि-समतल ग्राफ के किनारों की संख्या की सीमा को पूरा करते हैं। हालाँकि, द्वि-समतल ग्राफ (या पृथ्वी-चंद्रमा मानचित्र) के रूप में उनका प्रतिनिधित्व मायावी बना हुआ है। अनुप्रयोग द्वि-समतल ग्राफ के रंगों के एक अनुप्रयोग में लघु परिपथ के लिए मुद्रित परिपथ बोर्डों का परीक्षण शामिल है। इन बोर्डों के भीतर विद्युत चालकों में क्रॉसिंग शामिल हैं, लेकिन उनकी निकटताओं को एक द्वि-समतल ग्राफ बनाने के लिए माना जा सकता है। इस ग्राफ को रंगने के बाद, एक ही रंग के सभी कंडक्टरों को एक दूसरे से जोड़ने के लिए अतिरिक्त सर्किटरी जोड़कर और विभिन्न रंगों के जोड़े के बीच कनेक्शन के लिए परीक्षण करके आसन्न कंडक्टरों के बीच शॉर्ट सर्किट का पता लगाया जा सकता है। कुछ सावधानी के साथ, इस विचार का उपयोग प्रति सर्किट आवश्यक परीक्षणों की संख्या को केवल चार तक कम करने के लिए किया जा सकता है। सामान्यीकरण समस्या के विभिन्न सामान्यीकरणों पर भी विचार किया गया है, जिसमें दो से अधिक ग्रहों या उन देशों के साथ समस्या के संस्करण शामिल हैं जिनके पास प्रति ग्रह एक से अधिक क्षेत्र हो सकते हैं। विशेष रूप से, मोटाई के ग्राफ (दो से अधिक ग्रहों के साथ मानचित्र का प्रतिनिधित्व करते हैं लेकिन प्रति ग्रह केवल एक क्षेत्र), अधिक सटीक (हालांकि अभी भी अपूर्ण) परिणाम ज्ञात हैं। इन आलेखों के लिए, क्रोमाटिक संख्या पृथ्वी-चंद्रमा समस्या में उपयोग किए गए उसी अपक्षय तर्क द्वारा अधिक से अधिक है। साथ ही, क्योंकि, शीर्षों के साथ एक पूर्ण ग्राफ की मोटाई होती है, जिसमें से कुछ ग्राफों को दिखाने के लिए रंगों की आवश्यकता होती है। इस प्रकार, इस मामले में, ऊपरी और निचली सीमाएँ एक दूसरे के दो रंगों के भीतर हैं। संदर्भ बाहरी लिंक ग्राफ रंग