Barnette's conjecture
बार्नेट का अनुमान ग्राफ सिद्धांत में एक अनसुलझी समस्या है, जो गणित की एक शाखा है, जो ग्राफ में हैमिल्टनियन चक्रों से संबंधित है। इसका नाम कैलिफोर्निया विश्वविद्यालय, डेविस में प्रोफेसर एमेरिटस डेविड डब्ल्यू. बार्नेट के नाम पर रखा गया है; यह बताता है कि प्रति शीर्ष तीन किनारों वाले प्रत्येक द्विदलीय पॉलीहेड्रल ग्राफ में हैमिल्टनियन चक्र होता है। परिभाषा एक समतलीय ग्राफ एक दिशाहीन ग्राफ है जिसे यूक्लिडियन तल में बिना किसी क्रॉसिंग के एम्बेड किया जा सकता है। एक समतलीय ग्राफ को पॉलीहेड्रल कहा जाता है यदि और केवल अगर यह 3-वर्टेक्स से जुड़ा हुआ है, यानी, यदि दो शीर्ष मौजूद नहीं हैं, जिन्हें हटाने से बाकी ग्राफ डिस्कनेक्ट हो जाएगा। एक ग्राफ द्विदलीय होता है यदि इसके शीर्षों को दो अलग-अलग रंगों से रंगा जा सकता है जैसे कि प्रत्येक किनारे में प्रत्येक रंग का एक अंतिम बिंदु हो। एक ग्राफ घन (या 3-नियमित) है यदि प्रत्येक शीर्ष ठीक तीन किनारों का अंतिम बिंदु है। अंत में, एक ग्राफ हैमिल्टनियन है यदि एक चक्र मौजूद है जो इसके प्रत्येक शीर्ष से ठीक एक बार गुजरता है। बार्नेट के अनुमान में कहा गया है कि प्रत्येक घन द्विदलीय पॉलीहेड्रल ग्राफ हैमिल्टनियन है। स्टेनिट्ज़ के प्रमेय के अनुसार, एक समतलीय ग्राफ एक उत्तल पॉलीहेड्रॉन के किनारों और शीर्षों का प्रतिनिधित्व करता है यदि और केवल तभी जब यह पॉलीहेड्रल हो। एक त्रि-आयामी पॉलीहेड्रॉन में एक घन ग्राफ होता है यदि और केवल तभी जब यह एक साधारण पॉलीहेड्रॉन हो। और, एक समतलीय ग्राफ द्विदलीय होता है यदि और केवल तभी, जब ग्राफ के समतलीय एम्बेडिंग में, सभी चेहरे के चक्रों की लंबाई सम हो। इसलिए, बार्नेट के अनुमान को एक समतुल्य रूप में कहा जा सकता हैः मान लीजिए कि एक त्रि-आयामी सरल उत्तल बहुफलक के प्रत्येक चेहरे पर किनारों की संख्या सम होती है। फिर, अनुमान के अनुसार, पॉलीहेड्रॉन के ग्राफ में हैमिल्टनियन चक्र होता है। इतिहास ने अनुमान लगाया कि प्रत्येक घन पॉलीहेड्रल ग्राफ हैमिल्टनियन है; इसे टैट के अनुमान के रूप में जाना जाने लगा। इसे 46 शीर्षों के साथ एक प्रति-उदाहरण का निर्माण करने वाले द्वारा अस्वीकृत किया गया था; अन्य शोधकर्ताओं ने बाद में और भी छोटे प्रति-उदाहरण पाए। हालाँकि, इनमें से कोई भी ज्ञात प्रति-उदाहरण द्विदलीय नहीं है। टुटे ने स्वयं अनुमान लगाया कि प्रत्येक घन 3-जुड़ा हुआ द्विदलीय ग्राफ हैमिल्टनियन है, लेकिन एक प्रति-उदाहरण, हॉर्टन ग्राफ की खोज से इसे गलत दिखाया गया। टेट और टुटे के अनुमानों के एक कमजोर संयोजन का प्रस्ताव करते हुए कहा कि प्रत्येक द्विदलीय घन पॉलीहेड्रॉन हैमिल्टनियन है, या, समकक्ष रूप से, कि टेट के अनुमान का प्रत्येक प्रति-उदाहरण गैर-द्विदलीय है। समतुल्य रूपों से पता चला कि बार्नेट का अनुमान एक सतही रूप से मजबूत कथन के बराबर है, कि एक द्विदलीय घन पॉलीहेड्रॉन के एक ही चेहरे पर प्रत्येक दो किनारों ई और एफ के लिए, एक हैमिल्टनियन चक्र मौजूद है जिसमें ई होता है लेकिन इसमें एफ नहीं होता है। स्पष्ट रूप से, यदि यह कथन सच है, तो प्रत्येक द्विदलीय घन पॉलीहेड्रॉन में हैमिल्टनियन चक्र होता हैः बस मनमाने ढंग से ई और एफ चुनें। अन्य दिशाओं में, केलमन्स ने दिखाया कि एक प्रति-उदाहरण को मूल बार्नेट अनुमान के प्रति-उदाहरण में बदला जा सकता है। बार्नेट का अनुमान भी इस कथन के बराबर है कि प्रत्येक घन द्विदलीय पॉलीहेड्रल ग्राफ के दोहरे के शीर्षों को दो उपसमुच्चय में विभाजित किया जा सकता है जिनके प्रेरित उपग्राफ पेड़ हैं। दोहरे ग्राफ में इस तरह के विभाजन द्वारा प्रेरित कटौती प्राथमिक ग्राफ में हैमिल्टनियन चक्र से मेल खाती है। आंशिक परिणाम हालांकि बार्नेट के अनुमान की सच्चाई अज्ञात है, कम्प्यूटेशनल प्रयोगों से पता चला है कि 86 से कम शीर्षों के साथ कोई प्रति-उदाहरण नहीं है। यदि बार्नेट का अनुमान गलत साबित होता है, तो यह परीक्षण करने के लिए एन. पी.-पूर्ण दिखाया जा सकता है कि क्या एक द्विदलीय घन पॉलीहेड्रॉन हैमिल्टनियन है। यदि एक समतलीय ग्राफ द्विदलीय और घन है लेकिन केवल संपर्क 2 का है, तो यह गैर-हैमिल्टोनियन हो सकता है, और इन ग्राफों के लिए हैमिल्टोनसिटी का परीक्षण करने के लिए यह एनपी-पूर्ण है। एक अन्य परिणाम इस प्रकार प्राप्त किया गया थाः यदि दोहरा ग्राफ नीले, लाल और हरे रंगों के साथ शीर्ष-रंग का हो सकता है जैसे कि प्रत्येक लाल-हरे चक्र में डिग्री 4 का शीर्ष हो, तो प्राथमिक ग्राफ हैमिल्टनियन है। संबंधित समस्याएं बार्नेट के एक संबंधित अनुमान में कहा गया है कि प्रत्येक घन पॉलीहेड्रल ग्राफ जिसमें सभी चेहरों के छह या उससे कम किनारे होते हैं, हैमिल्टनियन होता है। कम्प्यूटेशनल प्रयोगों से पता चला है कि, यदि एक विपरीत उदाहरण मौजूद है, तो इसमें 177 से अधिक शीर्ष होने चाहिए। अनुमान द्वारा सिद्ध किया गया था। इन दोनों अनुमानों का प्रतिच्छेदन यह होगा कि प्रत्येक द्विदलीय घन पॉलीहेड्रल ग्राफ जिसमें सभी चेहरों के चार या छह किनारे होते हैं, हैमिल्टनियन होता है। यह बात सच साबित हुई। टिप्पणियाँ संदर्भ; वैज्ञानिक पत्रों में पुनर्मुद्रित, खंड। II, पीपी। 85-98 बाहरी लिंक ओपन प्रॉब्लम गार्डन में बार्नेट का अनुमान, रॉबर्ट सामल, 2007। ग्राफ सिद्धांत में अनसुलझी समस्याओं के अनुमान प्लानर ग्राफ हैमिल्टनियन पथ और चक्र