ग्राफ कलरिंग
ग्राफ कलरिंग ग्राफ के तत्वों को लेबल, या रंग निर्दिष्ट करती है ताकि आसन्न तत्व भिन्न हों, और आवश्यक रंगों की न्यूनतम संख्या का अध्ययन करती है।
Definition
एक ग्राफ की उचित रंगाई उसके शीर्षों को रंगों का एक ऐसा असाइनमेंट है जिससे कोई भी दो आसन्न शीर्ष एक ही रंग साझा न करें; वर्णिक संख्या रंगों की वह न्यूनतम संख्या है जिसके लिए ऐसा असाइनमेंट मौजूद होता है।
Scope
यह विषय उचित शीर्ष रंगाई और वर्णिक संख्या, किनारा रंगाई और वर्णिक सूचकांक, रंगाई की गणना करने वाला वर्णिक बहुपद, और ब्रुक्स प्रमेय, विज़िंग प्रमेय, और समतल ग्राफों के लिए चार रंग प्रमेय सहित महत्वपूर्ण परिणामों पर विचार करता है। यह रंगाई को स्वतंत्रता, गुटों और ग्राफ मापदंडों के व्यापक सिद्धांत से जोड़ता है।
Core questions
- किसी दिए गए ग्राफ को उचित रूप से रंगने के लिए कितने रंगों की न्यूनतम संख्या की आवश्यकता होती है?
- एक ग्राफ दिए गए पैलेट के साथ कितनी उचित रंगाई स्वीकार करता है?
- कौन से ग्राफ कम रंगों से रंगे जा सकते हैं, और कौन सी बाधाएं अधिक रंगों को मजबूर करती हैं?
- किनारा रंगाई और सूची रंगाई मूल धारणा को कैसे विस्तारित करती हैं?
Key concepts
- उचित शीर्ष रंगाई
- वर्णिक संख्या
- वर्णिक बहुपद
- किनारा रंगाई और वर्णिक सूचकांक
- ब्रुक्स प्रमेय
- चार रंग प्रमेय
Key theories
- चार रंग प्रमेय
- प्रत्येक समतल ग्राफ को अधिकतम चार रंगों से उचित रूप से रंगा जा सकता है, यह एक सदी से भी अधिक समय तक एक खुला कथन था और पहली बार 1976 में एपेल और हाकेन द्वारा व्यापक कंप्यूटर-सहायता प्राप्त केस विश्लेषण का उपयोग करके सिद्ध किया गया था।
- विज़िंग प्रमेय
- किसी भी सरल ग्राफ के किनारों को या तो अधिकतम डिग्री या अधिकतम डिग्री से एक अधिक रंगों से उचित रूप से रंगा जा सकता है, जिससे सभी ग्राफ दो संकीर्ण वर्गों में विभाजित हो जाते हैं।
Clinical relevance
कलरिंग संघर्ष-मुक्त संसाधन आवंटन को मॉडल करती है: बिना टकराव के शेड्यूलिंग, कंपाइलर में रजिस्टर आवंटन, वायरलेस नेटवर्क में आवृत्ति असाइनमेंट, और सुडोकू-शैली की बाधा समस्याएं सभी ग्राफ कलरिंग में कम हो जाती हैं।
History
1852 में प्रस्तुत चार रंग अनुमान ने कलरिंग सिद्धांत के अधिकांश भाग को प्रेरित किया; 1976 में एपेल और हाकेन द्वारा इसका कंप्यूटर-सहायता प्राप्त प्रमाण कंप्यूटर-सहायता प्राप्त गणित में एक प्रारंभिक मील का पत्थर था और इसने प्रमाण की प्रकृति के बारे में बहस छेड़ दी।
Debates
- कंप्यूटर-सहायता प्राप्त प्रमाणों की स्थिति
- चार रंग प्रमेय की मशीन-जांच किए गए मामलों पर निर्भरता ने यह सवाल उठाया कि क्या एक प्रमाण जो हाथ से सत्यापित करने के लिए मानव के लिए बहुत लंबा है, उसे एक वास्तविक गणितीय प्रमाण के रूप में गिना जाना चाहिए।
Key figures
- Kenneth Appel
- Wolfgang Haken
- Vadim Vizing
Related topics
Seminal works
- diestel2017
Frequently asked questions
- एक ग्राफ की वर्णिक संख्या क्या है?
- यह रंगों की सबसे छोटी संख्या है जिसकी आवश्यकता होती है ताकि आसन्न शीर्षों को हमेशा अलग-अलग रंग मिलें; उदाहरण के लिए, एक विषम चक्र की वर्णिक संख्या तीन होती है।
- क्या चार रंग प्रमेय सभी मानचित्रों पर लागू होता है?
- यह समतल या गोले पर खींचे गए मानचित्रों पर लागू होता है जहाँ क्षेत्र जुड़े होते हैं; टोरस जैसी सतहों पर बने मानचित्रों को अधिक रंगों की आवश्यकता हो सकती है।