शब्दकोष

बाईं ओर एक कीवर्ड चुनें ...

रेखांकन और नेटवर्कनक्शा रंग

पढ़ने का समय: ~15 min
इस पृष्ठ का स्वचालित रूप से अनुवाद किया गया है और इसमें त्रुटियां हो सकती हैं। कृपया हमसे संपर्क करें यदि आप अनुवादों की समीक्षा करने में हमारी सहायता करना चाहते हैं!

हमने पहले से ही कुछ नक्शे के साथ ग्राफ सिद्धांत का उपयोग किया है। जैसे ही हम बाहर ज़ूम करते हैं, व्यक्तिगत सड़कें और पुल गायब हो जाते हैं और इसके बजाय हम पूरे देशों की रूपरेखा देखते हैं।

जब नक्शा रंगना - या किसी अन्य ड्राइंग में अलग-अलग क्षेत्रों से मिलकर - आसन्न देशों में समान रंग नहीं हो सकता है। हम भी संभव के रूप में कुछ अलग रंगों का उपयोग करना चाहते हैं।

कुछ सरल "नक्शे", एक शतरंज की बिसात की तरह, केवल दो रंगों (काले और सफेद) की आवश्यकता होती है, लेकिन अधिकांश जटिल नक्शों की अधिक आवश्यकता होती है।

अमेरिकी राज्यों के नक्शे को रंगते समय, 50 रंग स्पष्ट रूप से पर्याप्त हैं, लेकिन बहुत कम आवश्यक हैं। नीचे दिए गए मानचित्रों को यथासंभव रंगों से रंगने का प्रयास करें:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

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

पहले की तरह, हम एक मानचित्र को देशों और सीमाओं के साथ एक प्लानर ग्राफ में बदल सकते हैं: हर देश बन जाता , और देश एक किनारे से एक जुड़ा हुआ है:

अब हम एक ग्राफ के कोने को रंग देना चाहते हैं, और दो कोने का एक अलग रंग होना चाहिए यदि वे एक किनारे से जुड़े हुए हैं।

1852 में, वनस्पति विज्ञान के छात्र फ्रांसिस गुथरी को इंग्लैंड में काउंटियों के मानचित्र को रंगना था। उन्होंने देखा कि चार रंग किसी भी मानचित्र के लिए पर्याप्त लग रहे थे, जो उन्होंने कोशिश की थी, लेकिन उन्हें ऐसा कोई प्रमाण नहीं मिला जो सभी मानचित्रों के लिए काम करता हो। यह एक अत्यंत कठिन समस्या बन गई और इसे चार रंग प्रमेय के रूप में जाना जाने लगा।

अगले 100 वर्षों के दौरान, कई गणितज्ञों ने चार रंग प्रमेय के लिए "सबूत" प्रकाशित किए, केवल बाद में पाए जाने वाली गलतियों के लिए। इन अमान्य सबूतों में से कुछ इतने ठोस थे कि त्रुटियों की खोज में 10 साल से अधिक का समय लग गया।

एक लंबे समय के लिए, गणितज्ञ यह साबित करने में असमर्थ थे कि चार रंग पर्याप्त हैं, या एक नक्शा खोजने के लिए जिसे चार से अधिक रंगों की आवश्यकता है।

1976 तक चार रंग समस्या पर थोड़ी प्रगति की गई थी, जब वोल्फगैंग होकेन और केनेथ अपेल ने अंत में इसे हल करने के लिए एक कंप्यूटर का उपयोग किया था। उन्होंने 1936 के विशेष मामलों में असीम रूप से कई संभावित मानचित्रों को कम कर दिया, जो प्रत्येक कंप्यूटर द्वारा 1000 घंटे से अधिक समय के लिए जांचे गए थे।

चार रंग प्रमेय एक कंप्यूटर का उपयोग करके सिद्ध किया जाने वाला पहला प्रसिद्ध गणितीय प्रमेय है, ऐसा कुछ जो तब से बहुत अधिक सामान्य और कम विवादित हो गया है। तेज़ कंप्यूटर और अधिक कुशल एल्गोरिदम का मतलब है कि आज आप कुछ घंटों में लैपटॉप पर चार रंग प्रमेय साबित कर सकते हैं।

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

चार रंग प्रमेय केवल एक समतल विमान या एक क्षेत्र पर नक्शों के लिए काम करते हैं, और जहाँ सभी देश एक ही क्षेत्र से मिलकर बने होते हैं।

हालांकि गणितज्ञों ने साम्राज्यों के मानचित्रों पर भी ध्यान दिया है, जहां देशों में कई डिस्कनेक्ट किए गए घटक शामिल हो सकते हैं, और अलग-अलग आकार के ग्रहों पर, जैसे कि एक टोरस (डोनट आकार)। इन मामलों में आपको चार से अधिक रंगों की आवश्यकता हो सकती है और प्रमाण और भी कठिन हो जाते हैं।

This map on a torus requires seven colours.

Archie