Hadwiger conjecture (graph theory)
ग्राफ सिद्धांत में, हैडविगर अनुमान में कहा गया है कि यदि लूपलेस है और कोई माइनर नहीं है तो इसकी क्रोमेटिक संख्या संतुष्ट करती है यह चार-रंग प्रमेय का सामान्यीकरण है और इसे क्षेत्र में सबसे महत्वपूर्ण और चुनौतीपूर्ण खुली समस्याओं में से एक माना जाता है। अधिक विस्तार से, यदि एक दिशाहीन ग्राफ के सभी उचित रंग या अधिक रंगों का उपयोग करते हैं, तो कोई भी ऐसे असंबद्ध जुड़े हुए उपग्राफ पा सकता है कि प्रत्येक उपग्राफ एक दूसरे के उपग्राफ से एक किनारे से जुड़ा हो। इन उपग्राफों में से प्रत्येक के भीतर किनारों को संकुचित करना ताकि प्रत्येक उपग्राफ एक ही शीर्ष पर गिर जाए, एक छोटे के रूप में शीर्षों पर एक पूर्ण ग्राफ उत्पन्न करता है यह अनुमान, चार रंग की समस्या का एक दूरगामी सामान्यीकरण, ह्यूगो हैडविगर द्वारा 1943 में बनाया गया था और अभी भी अनसुलझा है। इसे "ग्राफ सिद्धांत में सबसे गहरी अनसुलझी समस्याओं में से एक" कहते हैं। समतुल्य रूप हैडविगर अनुमान का एक समतुल्य रूप (ऊपर बताए गए रूप का विरोधाभासी) यह है कि, यदि किनारे के संकुचन का कोई क्रम नहीं है (प्रत्येक किसी किनारे के दो अंतिम बिंदुओं को एक एकल सुपरवर्टेक्स में विलय करता है) जो एक ग्राफ को पूरी तरह से लाता है तो रंगों के साथ एक शीर्ष रंग होना चाहिए। हालांकि, यह संकुचन प्रक्रिया एक मामूली उत्पादन नहीं करती है क्योंकि (परिभाषा के अनुसार) एक ही रंग वर्ग में किसी भी दो शीर्षों के बीच कोई किनारा नहीं होता है, इस प्रकार संकुचन एक किनारे का संकुचन नहीं है (जो नाबालिगों के लिए आवश्यक है)। हैडविगर के अनुमान में कहा गया है कि एकल शीर्षों के लिए शीर्षों के संरेखण सेट के ठीक से किनारे का एक अलग तरीका मौजूद है, जो इस तरह से एक पूर्ण उत्पादन करता है कि सभी संरेखित सेट जुड़े हुए हैं। यदि ग्राफ के परिवार को दर्शाता है जिसमें वह गुण है जिसमें ग्राफ के सभी नाबालिग हो सकते हैं तो यह रॉबर्टसन-सीमोर प्रमेय से मिलता है जिसे निषिद्ध नाबालिगों के एक सीमित समूह द्वारा चिह्नित किया जा सकता है। हैडविगर का अनुमान है कि इस सेट में एक ही निषिद्ध सेट होता है एक ग्राफ की हैडविगर संख्या सबसे बड़े पूर्ण ग्राफ का आकार है जो कि एक मामूली है (या समतुल्य रूप से संकुचन किनारों द्वारा प्राप्त किया जा सकता है) इसे संकुचन गुट संख्या के रूप में भी जाना जाता है हैडविगर अनुमान को सरल बीजगणितीय रूप में कहा जा सकता है जहां रंगीन संख्या विशेष मामलों और आंशिक परिणामों को दर्शाता है। मामला भी आसान हैः तीन रंगों की आवश्यकता वाले ग्राफ गैर-द्विदलीय ग्राफ हैं, और प्रत्येक गैर-द्विदलीय ग्राफ में एक विषम चक्र होता है, जिसे 3-चक्र, यानी एक छोटे चक्र में संकुचित किया जा सकता है। उसी पेपर में जिसमें उन्होंने अनुमान पेश किया था, हैडविगर ने इसकी सच्चाई को साबित किया-बिना किसी मामूली के ग्राफ श्रृंखला-समानांतर ग्राफ और उनके उपग्राफ हैं। इस प्रकार के प्रत्येक ग्राफ में अधिकतम दो आपतित किनारों के साथ एक शीर्ष होता है; कोई भी ऐसे किसी भी ग्राफ को ऐसे एक शीर्ष को हटाकर, शेष ग्राफ को पुनरावर्ती रूप से रंगकर, और फिर वापस जोड़कर और हटाए गए शीर्ष को रंगकर 3-रंग कर सकता है। क्योंकि हटाए गए शीर्ष में अधिक से अधिक दो किनारे होते हैं, जब शीर्ष को वापस जोड़ा जाता है तो तीन रंगों में से एक हमेशा इसे रंगने के लिए उपलब्ध रहेगा। के लिए अनुमान की सच्चाई चार रंग प्रमेय का तात्पर्य हैः क्योंकि, यदि अनुमान सही है, तो पाँच या अधिक रंगों की आवश्यकता वाले प्रत्येक ग्राफ में एक छोटा होगा और (वैगनर के प्रमेय के अनुसार) गैर-समतल होगा। क्लाउस वैगनर ने 1937 में साबित किया कि यह मामला वास्तव में चार रंग प्रमेय के बराबर है और इसलिए अब हम जानते हैं कि यह सच है। जैसा कि वैगनर ने दिखाया, प्रत्येक ग्राफ जिसमें कोई छोटा नहीं होता है, उसे क्लीक-सम के माध्यम से टुकड़ों में विघटित किया जा सकता है जो या तो समतल या 8-वर्टेक्स मोबियस सीढ़ी होते हैं, और इनमें से प्रत्येक टुकड़े एक दूसरे से स्वतंत्र रूप से 4-रंग के हो सकते हैं, इसलिए एक-लघु-मुक्त ग्राफ की 4-रंगनीयता प्रत्येक समतल टुकड़ों की 4-रंगनीयता से होती है। चार रंग प्रमेय का उपयोग करके भी अनुमान को साबित किया; इस प्रमाण के साथ उनके शोध पत्र ने 1994 का फुल्करसन पुरस्कार जीता। यह उनके प्रमाण से पता चलता है कि प्लैनर ग्राफ के एक त्रि-आयामी अनुरूप, लिंकलेस एम्बेडेबल ग्राफ में अधिकतम पांच क्रोमाटिक संख्या होती है। इस परिणाम के कारण, अनुमान को सही माना जाता है लेकिन यह अभी भी अनसुलझा है क्योंकि, कुछ आंशिक परिणाम ज्ञात हैंः प्रत्येक 7-वर्णात्मक ग्राफ में या तो एक छोटा या एक छोटा और एक छोटा दोनों होना चाहिए। प्रत्येक ग्राफ में अधिकांश घटना किनारों के साथ एक शीर्ष होता है, जिससे यह पता चलता है कि एक लालची रंग एल्गोरिथ्म जो इस निम्न-डिग्री शीर्ष को हटा देता है, शेष ग्राफ को रंग देता है, और फिर हटाए गए शीर्ष को वापस जोड़ता है और इसे रंग देता है, दिए गए ग्राफ को रंगों से रंग देगा। 1980 के दशक में, अलेक्जेंडर वी. कोस्टोचका और एंड्रयू थॉमसन दोनों ने स्वतंत्र रूप से साबित किया कि प्रत्येक ग्राफ में औसत डिग्री होती है और इस प्रकार रंगों का उपयोग करके रंगीन किया जा सकता है। इस सीमा में सुधारों के एक क्रम ने सामान्यीकरण के बिना ग्राफों के लिए-वर्णनीयता की घोषणा की है ग्योरगी हाजोस ने अनुमान लगाया कि हैडविगर के अनुमान को नाबालिगों के बजाय उपखंडों में मजबूत किया जा सकता हैः यानी, रंगीन संख्या वाले प्रत्येक ग्राफ में एक पूर्ण हाजोस के अनुमान का एक उपखंड होता है जो सच है, लेकिन इस मजबूत अनुमान के मामलों के विपरीत उदाहरण पाए जाते हैं और देखा जाता है कि हाजोस का अनुमान यादृच्छिक ग्राफों के लिए बुरी तरह विफल रहता हैः क्योंकि सीमा में जैसे-जैसे शीर्षों की संख्या, अनंत तक जाती है, संभावना एक तक पहुंचती है कि एक यादृच्छिक ग्राफ में वर्णात्मक होता है और इसके सबसे बड़े गुट उपखंड में शीर्ष होते हैं। इस संदर्भ में, यह ध्यान देने योग्य है कि संभावना यह भी है कि एक यादृच्छिक ग्राफ में हैडविगर संख्या इसकी रंगीन संख्या से अधिक या उसके बराबर होती है, इसलिए हैडविगर अनुमान उच्च संभावना वाले यादृच्छिक ग्राफ के लिए रखता है; अधिक सटीक रूप से, हैडविगर संख्या उच्च संभावना के साथ आनुपातिक है यह पूछे जाने पर कि क्या हैडविगर के अनुमान को सूची रंग तक बढ़ाया जा सकता है। सूची वर्णात्मक संख्या वाले प्रत्येक ग्राफ में एक गुट लघु होता है। हालांकि, समतल ग्राफ की अधिकतम सूची वर्णात्मक संख्या 5 है, 4 नहीं, इसलिए विस्तार पहले से ही ग्राफ के लिए विफल हो जाता है। अधिक आम तौर पर, ऐसे ग्राफ मौजूद हैं जिनकी हैडविगर संख्या है और जिनकी सूची क्रोमेटिक संख्या गेरार्ड्स और सीमोर ने अनुमान लगाया है कि क्रोमेटिक संख्या वाले प्रत्येक ग्राफ में एक विषम लघु के रूप में एक पूर्ण ग्राफ होता है। इस तरह की संरचना को शीर्ष-विच्छेदित उप-वृक्षों के परिवार के रूप में दर्शाया जा सकता है, जिनमें से प्रत्येक दो रंग का होता है, जैसे कि उप-वृक्षों की प्रत्येक जोड़ी एक एकवर्णी किनारे से जुड़ी होती है। हालांकि बिना विषम लघु वाले ग्राफ आवश्यक रूप से विरल नहीं होते हैं, लेकिन उनके लिए एक समान ऊपरी सीमा वैसी ही होती है जैसी मानक हैडविगर अनुमान के लिए होती हैः बिना विषम लघु वाले ग्राफ में रंगीन संख्या होती है। अतिरिक्त शर्तों को लागू करने से, बड़े नाबालिगों के अस्तित्व को साबित करना संभव हो सकता है। एक उदाहरण स्नार्क प्रमेय है, कि किसी भी किनारे के रंग में चार रंगों की आवश्यकता वाले प्रत्येक घन ग्राफ में पीटरसन ग्राफ एक छोटे के रूप में होता है, जिसका अनुमान डब्ल्यू. टी. टुटे द्वारा लगाया गया है और 2001 में रॉबर्टसन, सैंडर्स, सीमोर और थॉमस द्वारा साबित करने की घोषणा की गई थी। टिप्पणियाँ संदर्भ ग्राफ रंग ग्राफ लघु सिद्धांत अनुमान ग्राफ सिद्धांत में अनसुलझी समस्याएं