Halin graph
ग्राफ सिद्धांत में, एक हेलिन ग्राफ एक प्रकार का समतलीय ग्राफ है, जिसका निर्माण एक पेड़ की पत्तियों को एक चक्र में जोड़कर किया जाता है। पेड़ में कम से कम चार शीर्ष होने चाहिए, जिनमें से किसी के भी ठीक दो पड़ोसी नहीं हैं; इसे समतल में खींचा जाना चाहिए ताकि इसका कोई भी किनारा पार न हो (इसे समतल एम्बेडिंग कहा जाता है), और चक्र इस एम्बेडिंग में पत्तियों को उनके घड़ी की दिशा में क्रम में जोड़ता है। इस प्रकार, चक्र हेलिन ग्राफ का बाहरी चेहरा बनाता है, जिसके अंदर पेड़ होता है। हेलिन ग्राफ का नाम जर्मन गणितशास्त्री रुडोल्फ हेलिन के नाम पर रखा गया है, जिन्होंने 1971 में उनका अध्ययन किया था। घन हेलिन ग्राफ-जिनमें प्रत्येक शीर्ष ठीक तीन किनारों को छूता है-का अध्ययन किर्कमैन द्वारा एक सदी पहले ही किया जा चुका था। हेलिन ग्राफ पॉलीहेड्रल ग्राफ हैं, जिसका अर्थ है कि प्रत्येक हेलिन ग्राफ का उपयोग उत्तल पॉलीहेड्रॉन के शीर्ष और किनारों को बनाने के लिए किया जा सकता है, और उनसे बने पॉलीहेड्रा को छत रहित पॉलीहेड्रा या गुंबद कहा जाता है। प्रत्येक हेलिन ग्राफ में अपने सभी शीर्षों के माध्यम से एक हैमिल्टनियन चक्र होता है, साथ ही ग्राफ के शीर्षों की संख्या तक लगभग सभी लंबाई के चक्र होते हैं। हेलिन ग्राफ को रैखिक समय में पहचाना जा सकता है। क्योंकि हैलिन ग्राफ में कम त्रि-चौड़ाई होती है, कई कम्प्यूटेशनल समस्याएं जो अन्य प्रकार के समतलीय ग्राफ पर कठिन होती हैं, जैसे कि हैमिल्टनियन चक्रों का पता लगाना, को हैलिन ग्राफ पर जल्दी से हल किया जा सकता है। उदाहरण-एक तारा एक ऐसा वृक्ष है जिसका एक आंतरिक शीर्ष होता है। एक तारे पर हेलिन ग्राफ निर्माण को लागू करने से एक चक्र ग्राफ, एक पिरामिड (के किनारों) का ग्राफ उत्पन्न होता है। एक त्रिकोणीय प्रिज्म का ग्राफ भी एक हेलिन ग्राफ हैः इसे इस तरह से खींचा जा सकता है कि इसका एक आयताकार चेहरा बाहरी चक्र हो, और शेष किनारे चार पत्तियों, दो आंतरिक शीर्षों और पांच किनारों के साथ एक पेड़ बनाते हैं। फ्रुक्ट ग्राफ, पाँच सबसे छोटे घन ग्राफों में से एक है जिसमें कोई गैर-तुच्छ ग्राफ ऑटोमोर्फिज्म नहीं है, यह भी एक हेलिन ग्राफ है। गुण प्रत्येक हेलिन ग्राफ 3-जुड़ा हुआ है, जिसका अर्थ है कि इससे दो शीर्षों को हटाना और शेष शीर्षों को अलग करना संभव नहीं है। यह एज-मिनिमल 3-कनेक्टेड है, जिसका अर्थ है कि यदि इसके किसी भी किनारे को हटा दिया जाता है, तो शेष ग्राफ अब 3-कनेक्टेड नहीं होगा। स्टेनिट्ज़ के प्रमेय के अनुसार, एक 3-जुड़े हुए समतलीय ग्राफ के रूप में, इसे एक उत्तल पॉलीहेड्रॉन के शीर्षों और किनारों के समूह के रूप में दर्शाया जा सकता है; यानी, यह एक पॉलीहेड्रल ग्राफ है। ग्राफ को महसूस करने वाले पॉलीहेड्रॉन को चुना जा सकता है ताकि पेड़ के सभी पत्तों वाला चेहरा क्षैतिज हो, और अन्य सभी चेहरे इसके ऊपर समान ढलानों के साथ हों। प्रत्येक पॉलीहेड्रल ग्राफ की तरह, हेलिन ग्राफ में एक अद्वितीय समतलीय एम्बेडिंग होती है, जो इस बात पर निर्भर करती है कि इसका कौन सा चेहरा बाहरी चेहरा होना चाहिए। प्रत्येक हेलिन ग्राफ एक हैमिल्टनियन ग्राफ है, और ग्राफ का प्रत्येक किनारा हैमिल्टनियन चक्र से संबंधित है। इसके अलावा, किसी भी शीर्ष को हटाने के बाद कोई भी हेलिन ग्राफ हैमिल्टनियन बना रहता है। क्योंकि डिग्री 2 के शीर्ष के बिना प्रत्येक पेड़ में दो पत्ते होते हैं जो एक ही मूल को साझा करते हैं, प्रत्येक हेलिन ग्राफ में एक त्रिकोण होता है। विशेष रूप से, हेलिन ग्राफ के लिए त्रिभुज-मुक्त ग्राफ और न ही द्विदलीय ग्राफ होना संभव नहीं है। अधिक दृढ़ता से, प्रत्येक हेलिन ग्राफ लगभग पैनसाइक्लिक होता है, इस अर्थ में कि इसमें एकल सम लंबाई के संभावित अपवाद के साथ 3 से n तक की सभी लंबाई के चक्र होते हैं। इसके अलावा, यदि एक भी किनारा संकुचित हो जाता है तो कोई भी हेलिन ग्राफ लगभग पैनसाइक्लिक रहता है, और डिग्री तीन के आंतरिक शीर्षों के बिना प्रत्येक हेलिन ग्राफ पैनसाइक्लिक होता है। अधिकतम डिग्री चार से अधिक के साथ एक हेलिन ग्राफ की आपतन वर्णात्मक संख्या है। यह सभी जोड़े (v, e) को रंग देने के लिए आवश्यक रंगों की संख्या है जहां v ग्राफ का एक शीर्ष है, और e, रंग पर कुछ बाधाओं का पालन करते हुए, v के लिए एक किनारे की घटना है। जो जोड़े एक शीर्ष साझा करते हैं या जो एक किनारे को साझा करते हैं, उन्हें एक ही रंग की अनुमति नहीं है। इसके अलावा, एक जोड़ी (v, e) का रंग दूसरे जोड़े के समान नहीं हो सकता है जो e के दूसरे अंतिम बिंदु का उपयोग करता है। या के साथ हेलिन ग्राफ के लिए, आपतन वर्णात्मक संख्या उतनी ही बड़ी या क्रमशः हो सकती है। कम्प्यूटेशनल जटिलता यह परीक्षण करना संभव है कि क्या दिया गया-वर्टेक्स ग्राफ रैखिक समय में एक हेलिन ग्राफ है, ग्राफ की एक समतलीय एम्बेडिंग (यदि एक मौजूद है) का पता लगाकर, और फिर यह परीक्षण करके कि क्या कोई ऐसा चेहरा मौजूद है जिसमें कम से कम शीर्ष हैं, सभी डिग्री तीन के हैं। यदि ऐसा है, तो ऐसे अधिक से अधिक चार चेहरे हो सकते हैं, और उनमें से प्रत्येक के लिए रैखिक समय में यह जांचना संभव है कि क्या बाकी ग्राफ इस चेहरे के शीर्षों के साथ एक पेड़ बनाता है। दूसरी ओर, यदि ऐसा कोई चेहरा मौजूद नहीं है, तो ग्राफ हेलिन नहीं है। वैकल्पिक रूप से, शीर्षों और किनारों के साथ एक ग्राफ हेलिन होता है और केवल तभी जब यह समतल, 3-जुड़ा हुआ होता है, और इसका एक चेहरा होता है जिसके शीर्षों की संख्या ग्राफ की परिपथ श्रेणी के बराबर होती है, जिनमें से सभी को रैखिक समय में जांचा जा सकता है। रैखिक समय में हेलिन ग्राफ को पहचानने के लिए अन्य तरीकों में कोरसेल के प्रमेय का अनुप्रयोग, या ग्राफ पुनर्लेखन पर आधारित एक विधि शामिल है, जिनमें से कोई भी ग्राफ के समतल एम्बेडिंग को जानने पर निर्भर नहीं है। प्रत्येक हेलिन ग्राफ की त्रि-चौड़ाई = 3 होती है। इसलिए, कई ग्राफ अनुकूलन समस्याएं जो मनमाने समतलीय ग्राफ के लिए एन. पी.-पूर्ण हैं, जैसे कि अधिकतम स्वतंत्र सेट खोजना, गतिशील प्रोग्रामिंग या कोरसेल के प्रमेय का उपयोग करके हेलिन ग्राफ पर रैखिक समय में हल किया जा सकता है, या कुछ मामलों में (जैसे कि हैमिल्टनियन चक्रों का निर्माण) प्रत्यक्ष एल्गोरिदम द्वारा। हालांकि, किसी दिए गए ग्राफ का सबसे बड़ा हेलिन सबग्राफ खोजना एनपी-पूर्ण है, यह परीक्षण करने के लिए कि क्या कोई हेलिन सबग्राफ मौजूद है जिसमें दिए गए ग्राफ के सभी शीर्ष शामिल हैं, या यह परीक्षण करने के लिए कि क्या दिया गया ग्राफ एक बड़े हेलिन ग्राफ का सबग्राफ है। 1971 में, हेलिन ने न्यूनतम 3-वर्टेक्स से जुड़े ग्राफ के एक वर्ग के रूप में हेलिन ग्राफ की शुरुआत कीः ग्राफ में हर किनारे के लिए, उस किनारे को हटाने से ग्राफ की कनेक्टिविटी कम हो जाती है। इन आलेखों ने इस खोज के साथ महत्व प्राप्त किया कि कई एल्गोरिदमिक समस्याएं जो मनमाने ढंग से समतलीय आलेखों के लिए कम्प्यूटेशनल रूप से अव्यवहार्य थीं, उन पर कुशलता से हल की जा सकती हैं। इस तथ्य को बाद में उनकी कम त्रि-चौड़ाई और कॉर्सेल के प्रमेय जैसे एल्गोरिथमिक मेटा-प्रमेयों का परिणाम बताया गया जो कम त्रि-चौड़ाई के किसी भी ग्राफ पर इन समस्याओं का कुशल समाधान प्रदान करते हैं। इन ग्राफों पर हेलिन के काम से पहले, क्यूबिक (या 3-नियमित) हेलिन ग्राफ से संबंधित ग्राफ गणना समस्याओं का अध्ययन 1856 में थॉमस किर्कमैन और 1965 में हंस राडेमाकर द्वारा किया गया था। राडेमाकर इन ग्राफों को पॉलीहेड्रा आधारित कहते हैं। वह उन्हें क्यूबिक पॉलीहेड्रल ग्राफ के रूप में परिभाषित करता है जिसमें चेहरे होते हैं जिनमें से एक चेहरे के किनारे होते हैं। इस परिभाषा में फिट होने वाले ग्राफ बिल्कुल घन हेलिन ग्राफ हैं। इस तथ्य से प्रेरित कि हेलिन ग्राफ और 4-वर्टेक्स से जुड़े समतलीय ग्राफ दोनों में हैमिल्टनियन चक्र होते हैं, यह अनुमान लगाया गया कि प्रत्येक 4-वर्टेक्स से जुड़े समतलीय ग्राफ में एक फैला हुआ हेलिन उपग्राफ होता है; यहाँ "फैलाव" का अर्थ है कि उपग्राफ में बड़े ग्राफ के सभी शीर्ष शामिल हैं। लोवाज़-प्लमर अनुमान 2015 तक खुला रहा, जब असीम रूप से कई प्रति-उदाहरणों के लिए एक निर्माण प्रकाशित किया गया था। हेलिन ग्राफ को कभी-कभी स्कर्टेड ट्री या रूफलेस पॉलीहेड्रा भी कहा जाता है। हालाँकि, ये नाम अस्पष्ट हैं। कुछ लेखक पत्तियों को एक चक्र में जोड़कर पेड़ों से बने समतल ग्राफ को संदर्भित करने के लिए "स्कर्टेड ट्रीज़" नाम का उपयोग करते हैं, लेकिन यह आवश्यक नहीं है कि पेड़ के आंतरिक शीर्षों में डिग्री तीन या उससे अधिक हो। और "आधारित पॉलीहेड्रा" की तरह, "छत रहित पॉलीहेड्रा" नाम भी घन हेलिन ग्राफ को संदर्भित कर सकता है। उत्तल पॉलीहेड्रा, जिनके ग्राफ हेलिन ग्राफ हैं, उन्हें भी गुंबद कहा जाता है। संदर्भ बाहरी लिंक हेलिन ग्राफ, ग्राफ वर्ग समावेशन पर सूचना प्रणाली। ग्राफ परिवार प्लानर ग्राफ