Well-covered graph
ग्राफ सिद्धांत में, एक अच्छी तरह से ढका हुआ ग्राफ एक दिशाहीन ग्राफ है जिसमें प्रत्येक न्यूनतम शीर्ष आवरण का आकार प्रत्येक अन्य न्यूनतम शीर्ष आवरण के समान होता है। समान रूप से, ये वे ग्राफ हैं जिनमें सभी अधिकतम स्वतंत्र सेटों का आकार समान होता है। अच्छी तरह से ढके हुए ग्राफ को परिभाषित किया गया था और पहली बार 1970 में माइकल डी. प्लमर द्वारा अध्ययन किया गया था। अच्छी तरह से ढके हुए ग्राफ में सभी पूर्ण ग्राफ, संतुलित पूर्ण द्विदलीय ग्राफ शामिल हैं, और रुक के ग्राफ जिनके शीर्ष शतरंज की बिसात के वर्गों का प्रतिनिधित्व करते हैं और किनारे शतरंज की रुक की चाल का प्रतिनिधित्व करते हैं। अच्छी तरह से ढके हुए घन ग्राफों के ज्ञात लक्षण वर्णन, अच्छी तरह से ढके हुए पंजे-मुक्त ग्राफ और उच्च परिधि के अच्छी तरह से ढके हुए ग्राफ इन ग्राफों को बहुपद समय में पहचाने जाने की अनुमति देते हैं, लेकिन यह परीक्षण करना कि क्या अन्य प्रकार के ग्राफ अच्छी तरह से ढके हुए हैं, एक सीओएनपी-पूर्ण समस्या है। परिभाषा ग्राफ में एक शीर्ष आवरण शीर्षों का एक समूह है जो ग्राफ में हर किनारे को छूता है। एक शीर्ष आवरण न्यूनतम या अपरिवर्तनीय होता है, यदि इससे किसी भी शीर्ष को हटाने से आवरण गुण नष्ट हो जाएगा। यह न्यूनतम है यदि कम शीर्षों के साथ कोई अन्य शीर्ष आवरण नहीं है। एक अच्छी तरह से कवर किया गया ग्राफ वह होता है जिसमें प्रत्येक न्यूनतम कवर भी न्यूनतम होता है। अच्छी तरह से ढके हुए ग्राफ को परिभाषित करने वाले मूल पेपर में, प्लमर लिखते हैं कि यह "स्पष्ट रूप से इस गुण के बराबर" है कि हर दो न्यूनतम कवर में एक दूसरे के समान संख्या में शीर्ष होते हैं। ग्राफ में एक स्वतंत्र सेट शीर्षों का एक समूह है जिनमें से कोई दो एक दूसरे से सटे नहीं हैं। यदि एक ग्राफ में एक शीर्ष आवरण है, तो का पूरक एक स्वतंत्र सेट होना चाहिए, और इसके विपरीत। एक न्यूनतम शीर्ष आवरण है यदि और केवल तभी जब इसका पूरक एक अधिकतम स्वतंत्र समूह है, और एक न्यूनतम शीर्ष आवरण है यदि और केवल तभी जब इसका पूरक एक अधिकतम स्वतंत्र समूह है। इसलिए, एक अच्छी तरह से ढका हुआ ग्राफ, समतुल्य रूप से, एक ग्राफ है जिसमें प्रत्येक अधिकतम स्वतंत्र सेट का आकार समान होता है, या एक ग्राफ जिसमें प्रत्येक अधिकतम स्वतंत्र सेट अधिकतम होता है। अच्छी तरह से कवर किए गए ग्राफ को परिभाषित करने वाले मूल पेपर में, ये परिभाषाएँ जुड़े हुए ग्राफ तक ही सीमित थीं, हालाँकि वे डिस्कनेक्ट किए गए ग्राफ के लिए भी सार्थक हैं। बाद के कुछ लेखकों ने संपर्क आवश्यकता को कमजोर आवश्यकता के साथ बदल दिया है कि एक अच्छी तरह से ढके हुए ग्राफ में कोई अलग-थलग शीर्ष नहीं होना चाहिए। दोनों जुड़े हुए अच्छी तरह से ढके हुए ग्राफ और अलग-अलग शीर्षों के बिना अच्छी तरह से ढके हुए ग्राफ के लिए, कोई आवश्यक शीर्ष, शीर्ष नहीं हो सकते हैं जो प्रत्येक न्यूनतम शीर्ष आवरण से संबंधित हों। इसके अतिरिक्त, प्रत्येक अच्छी तरह से कवर किया गया ग्राफ शीर्ष को कवर करने के लिए एक महत्वपूर्ण ग्राफ है, इस अर्थ में कि प्रत्येक शीर्ष के लिए, ग्राफ से हटाने से एक छोटा न्यूनतम शीर्ष आवरण वाला ग्राफ उत्पन्न होता है। ग्राफ का स्वतंत्र परिसर एक सरल परिसर है जिसमें प्रत्येक स्वतंत्र सेट के लिए एक सिंप्लेक्स होता है। एक सरल परिसर को शुद्ध कहा जाता है यदि इसके सभी अधिकतम सरलीकरणों में समान कार्डिनलिटी हो, तो एक अच्छी तरह से ढका हुआ ग्राफ एक शुद्ध स्वतंत्रता परिसर के साथ एक ग्राफ के बराबर होता है। उदाहरण चार या पाँच लंबाई का एक चक्र ग्राफ अच्छी तरह से कवर किया गया हैः प्रत्येक मामले में, प्रत्येक अधिकतम स्वतंत्र सेट का आकार दो होता है। सात लंबाई का एक चक्र और तीन लंबाई का एक मार्ग भी अच्छी तरह से ढका हुआ है। प्रत्येक पूर्ण ग्राफ अच्छी तरह से कवर किया गया हैः प्रत्येक अधिकतम स्वतंत्र सेट में एक ही शीर्ष होता है। इसी तरह, प्रत्येक क्लस्टर ग्राफ (पूर्ण ग्राफ का एक अलग संयोजन) अच्छी तरह से कवर किया गया है। एक पूर्ण द्विदलीय ग्राफ को अच्छी तरह से कवर किया जाता है यदि इसके द्विदलीय विभाजन के दोनों पक्षों में शीर्षों की संख्या समान हो, क्योंकि ये इसके केवल दो अधिकतम स्वतंत्र सेट हैं। एक त्रिभुज-मुक्त ग्राफ का पूरक ग्राफ जिसमें कोई अलग-अलग शीर्ष नहीं होते हैं, अच्छी तरह से ढका होता हैः इसमें दो से बड़ा कोई स्वतंत्र सेट नहीं होता है, और प्रत्येक एकल शीर्ष को दो-शीर्ष स्वतंत्र सेट तक बढ़ाया जा सकता है। एक रुक का ग्राफ अच्छी तरह से कवर किया जाता हैः यदि कोई शतरंज की बिसात पर रुक का कोई भी सेट रखता है ताकि कोई दो रुक एक-दूसरे पर हमला न करें, तो शतरंज की बिसात की प्रत्येक पंक्ति और स्तंभ पर एक होने तक अधिक गैर-आक्रामक रुक रखना जारी रखना हमेशा संभव है। ग्राफ जिसके शीर्ष एक साधारण बहुभुज के विकर्ण होते हैं और जिनके किनारे एक दूसरे को पार करने वाले विकर्णों के जोड़े को जोड़ते हैं, वे अच्छी तरह से ढके होते हैं, क्योंकि इसके अधिकतम स्वतंत्र सेट बहुभुज के त्रिकोण होते हैं और सभी त्रिकोणों में समान संख्या में किनारे होते हैं। यदि कोई-वर्टेक्स ग्राफ है, तो एक-किनारे वाले ग्राफ का मूल उत्पाद (यानी, नए शीर्षों को जोड़कर बनाया गया ग्राफ, प्रत्येक डिग्री एक और प्रत्येक एक अलग शीर्ष से सटा हुआ) अच्छी तरह से ढका हुआ है। क्योंकि, एक अधिकतम स्वतंत्र सेट में पूरक सेट के डिग्री-एक पड़ोसियों के साथ एक मनमाना स्वतंत्र सेट होना चाहिए, और इसलिए इसका आकार होना चाहिए। अधिक आम तौर पर, किसी भी ग्राफ को एक गुट के आवरण (गुटों में शीर्षों का विभाजन) के साथ एक साथ दिए जाने पर, प्रत्येक गुट में एक और शीर्ष जोड़कर बनाया गया ग्राफ अच्छी तरह से ढका होता है; जड़ वाला उत्पाद इस निर्माण का विशेष मामला है जब इसमें एक-वर्टेक्स गुट होते हैं। इस प्रकार, प्रत्येक ग्राफ एक अच्छी तरह से ढके हुए ग्राफ का एक प्रेरित उपग्राफ है। द्विदलीयता, बहुत अच्छी तरह से कवर किए गए ग्राफ और परिधि एक बहुत अच्छी तरह से कवर किए गए ग्राफ को एक अच्छी तरह से कवर किए गए ग्राफ (संभवतः डिस्कनेक्ट किए गए, लेकिन बिना किसी अलग-अलग शीर्ष के) के रूप में परिभाषित करते हैं जिसमें प्रत्येक अधिकतम स्वतंत्र सेट (और इसलिए प्रत्येक न्यूनतम शीर्ष आवरण भी) में ठीक आधा होता है। इस परिभाषा में एक ग्राफ के मूल उत्पाद और एक आधुनिक ग्राफ शामिल हैं। उदाहरण के लिए, इसमें और द्वारा अध्ययन किए गए द्विदलीय अच्छी तरह से कवर किए गए ग्राफ भी शामिल हैंः अलग-अलग शीर्षों के बिना द्विदलीय ग्राफ में, किसी भी द्विदलीय विभाजन के दोनों पक्ष अधिकतम स्वतंत्र सेट (और न्यूनतम शीर्ष कवर) बनाते हैं, इसलिए यदि ग्राफ अच्छी तरह से कवर किया गया है तो दोनों तरफ समान रूप से कई शीर्ष होने चाहिए। शीर्षों के साथ एक अच्छी तरह से कवर किए गए ग्राफ में, अलग-अलग शीर्षों के बिना, अधिकतम स्वतंत्र सेट का आकार अधिक से अधिक होता है, इसलिए बहुत अच्छी तरह से कवर किए गए ग्राफ अच्छी तरह से कवर किए गए ग्राफ होते हैं जिनमें अधिकतम स्वतंत्र सेट का आकार जितना संभव हो उतना बड़ा होता है। एक द्विदलीय ग्राफ अच्छी तरह से कवर किया जाता है अगर और केवल तभी जब इसका उस गुण के साथ एक सही मिलान होता है, जिसमें हर किनारे के लिए, पड़ोसियों का प्रेरित उपग्राफ और एक पूर्ण द्विदलीय ग्राफ बनाता है। मिलान के संदर्भ में लक्षण वर्णन को द्विदलीय ग्राफ से बहुत अच्छी तरह से कवर किए गए ग्राफ तक बढ़ाया जा सकता हैः एक ग्राफ बहुत अच्छी तरह से तब कवर किया जाता है जब और केवल तभी जब इसका निम्नलिखित दो गुणों के साथ एक सही मिलान होता हैः का कोई भी किनारा त्रिभुज से संबंधित नहीं है, और यदि का एक किनारा तीन-किनारे वाले पथ का केंद्रीय किनारा है, तो पथ के दो अंतिम बिंदु आसन्न होने चाहिए। इसके अलावा, अगर बहुत अच्छी तरह से कवर किया गया है, तो हर सही मिलान इन गुणों को संतुष्ट करता है। पेड़ द्विदलीय आलेखों का एक विशेष मामला है, और यह परीक्षण कि क्या एक पेड़ अच्छी तरह से ढका हुआ है, अच्छी तरह से ढके हुए द्विदलीय आलेखों के लक्षण वर्णन के एक बहुत ही सरल विशेष मामले के रूप में संभाला जा सकता हैः यदि एक पेड़ दो से अधिक शीर्षों वाला है, तो यह अच्छी तरह से ढका हुआ है यदि और केवल तभी जब पेड़ का प्रत्येक गैर-पत्ती नोड बिल्कुल एक पत्ते के बगल में हो। समान लक्षण वर्णन उन आलेखों पर लागू होता है जो स्थानीय रूप से पेड़ जैसे होते हैं, इस अर्थ में कि प्रत्येक शीर्ष के कम व्यास वाले पड़ोस चक्रीय होते हैंः यदि एक आलेखों का परिधि आठ या उससे अधिक है (ताकि, प्रत्येक शीर्ष के लिए, तीन की दूरी के भीतर शीर्षों का उपलेख चक्रीय हो) तो यह अच्छी तरह से ढका हुआ है यदि और केवल तभी जब एक से अधिक डिग्री के प्रत्येक शीर्ष में एक डिग्री का बिल्कुल एक पड़ोसी हो। एक निकटता से संबंधित लेकिन अधिक जटिल लक्षण वर्णन पाँच या उससे अधिक परिधि के अच्छी तरह से ढके ग्राफ पर लागू होता है। नियमितता और समतलीयता घन (3-नियमित) अच्छी तरह से ढके ग्राफ को वर्गीकृत किया गया हैः उनमें कम संपर्क वाले घन ग्राफ के तीन अनंत परिवारों के साथ सात 3-जुड़े उदाहरण शामिल हैं। सात 3-जुड़े घन अच्छी तरह से ढके हुए ग्राफ हैं पूर्ण ग्राफ, त्रिकोणीय प्रिज्म और पंचकोणीय प्रिज्म के ग्राफ, ड्यूरर ग्राफ, उपयोगिता ग्राफ, एक Y-δ परिवर्तन द्वारा उपयोगिता ग्राफ से प्राप्त आठ-वर्टेक्स ग्राफ, और 14-वर्टेक्स सामान्यीकृत पीटरसन ग्राफ। इन ग्राफों में से पहले चार समतल ग्राफ हैं। वे केवल चार घन पॉलीहेड्रल ग्राफ (सरल उत्तल पॉलीहेड्रा के ग्राफ) हैं जो अच्छी तरह से ढके हुए हैं। ग्राफ में से चार (दो प्रिज्म, ड्यूरर ग्राफ और) सामान्यीकृत पीटरसन ग्राफ हैं। 1-और 2-जुड़े घन अच्छी तरह से ढके हुए ग्राफ सभी एक पथ या चक्र के नोड्स को ग्राफ के तीन टुकड़ों द्वारा प्रतिस्थापित करके बनाए जाते हैं जो लेबल करते हैं, और। टुकड़ों का उपयोग एक चक्र के नोड्स या पथ के आंतरिक नोड्स को बदलने के लिए किया जा सकता है, जबकि टुकड़े का उपयोग पथ के दो अंतिम नोड्स को बदलने के लिए किया जाता है। टुकड़े में एक पुल होता है, इसलिए एक पथ पर इस प्रतिस्थापन प्रक्रिया को करने और कुछ पथ नोड्स (और शेष नोड्स के लिए अन्य दो टुकड़े) को बदलने के लिए टुकड़े का उपयोग करने का परिणाम 1-वर्टेक्स से जुड़ा घन अच्छी तरह से ढका हुआ ग्राफ है। सभी 1-वर्टेक्स से जुड़े क्यूबिक अच्छी तरह से ढके हुए ग्राफ में यह रूप होता है, और ऐसे सभी ग्राफ समतल होते हैं। दो प्रकार के 2-वर्टेक्स से जुड़े क्यूबिक अच्छी तरह से ढके हुए ग्राफ हैं। इन दो परिवारों में से एक का गठन एक चक्र के नोड्स को टुकड़ों द्वारा प्रतिस्थापित करके किया जाता है और कम से कम दो टुकड़े प्रकार के होते हैं; इस प्रकार का एक ग्राफ समतल होता है यदि और केवल तभी जब इसमें प्रकार के कोई टुकड़े न हों। दूसरा परिवार एक पथ के नोड्स को प्रकार के टुकड़ों द्वारा प्रतिस्थापित करके बनाया जाता है और; ऐसे सभी ग्राफ समतल होते हैं। तीन आयामों में अच्छी तरह से ढके हुए सरल पॉलीहेड्रा के लक्षण वर्णन को पूरा करते हुए, शोधकर्ताओं ने अच्छी तरह से ढके हुए सरल पॉलीहेड्रा, या समकक्ष रूप से अच्छी तरह से ढके हुए अधिकतम समतल ग्राफ पर भी विचार किया है। पाँच या अधिक शीर्षों वाले प्रत्येक अधिकतम समतलीय ग्राफ में शीर्ष संपर्क 3,4 या 5 होता है। कोई अच्छी तरह से कवर किए गए 5-जुड़े अधिकतम समतल ग्राफ नहीं हैं, और केवल चार 4-जुड़े हुए अच्छी तरह से कवर किए गए अधिकतम समतल ग्राफ हैंः नियमित ऑक्टाहेड्रॉन के ग्राफ, पंचकोणीय द्विध्रुवीय, स्नब डिस्पेनॉइड, और 12 शीर्षों, 30 किनारों और 20 त्रिकोणीय चेहरों के साथ एक अनियमित पॉलीहेड्रॉन (एक गैर-उत्तल डेल्टा)। हालाँकि, असीम रूप से कई 3-जुड़े हुए अच्छी तरह से ढके हुए अधिकतम समतल ग्राफ हैं। उदाहरण के लिए, यदि एक-वर्टेक्स अधिकतम समतलीय ग्राफ में अलग-अलग त्रिभुज चेहरे हैं, तो ये चेहरे एक गुट आवरण का निर्माण करेंगे। इसलिए, गुट आवरण निर्माण, जिसमें इन ग्राफों में से प्रत्येक को एक केंद्रीय शीर्ष पर मिलने वाले तीन नए त्रिकोणों में उपविभाजित करना शामिल है, एक अच्छी तरह से ढके हुए अधिकतम समतलीय ग्राफ का उत्पादन करता है। जटिलता परीक्षण कि क्या एक ग्राफ में विभिन्न आकारों के दो अधिकतम स्वतंत्र सेट होते हैं, एन. पी.-पूर्ण है; अर्थात, पूरक रूप से, यह परीक्षण करना कि क्या एक ग्राफ अच्छी तरह से कवर किया गया है, सी. ओ. एन. पी.-पूर्ण है। यद्यपि ग्राफों में अधिकतम स्वतंत्र सेटों को खोजना आसान है जिन्हें अच्छी तरह से कवर किया गया है, लेकिन एक एल्गोरिथ्म के लिए आउटपुट के रूप में उत्पादन करना भी एन. पी.-कठिन है, सभी ग्राफों पर, या तो अधिकतम स्वतंत्र सेट या एक गारंटी कि इनपुट अच्छी तरह से कवर नहीं है। इसके विपरीत, यह परीक्षण करना संभव है कि क्या दिया गया ग्राफ बहुपद समय में बहुत अच्छी तरह से कवर किया गया है। ऐसा करने के लिए, किनारों से युक्त उपलेख का पता लगाएं जो एक बहुत अच्छी तरह से ढके हुए ग्राफ में एक मिलान वाले किनारे के दो गुणों को संतुष्ट करते हैं, और फिर यह परीक्षण करने के लिए एक मिलान एल्गोरिथ्म का उपयोग करें कि क्या एक सही मिलान है। कुछ समस्याएं जो मनमाने ग्राफ के लिए एन. पी.-पूर्ण हैं, जैसे कि हैमिल्टनियन चक्र खोजने की समस्या, बहुत अच्छी तरह से कवर किए गए ग्राफ के लिए बहुपद समय में भी हल की जा सकती हैं। एक ग्राफ को समतुल्य कहा जाता है यदि प्रत्येक अधिकतम मिलान अधिकतम है; यानी, यह समतुल्य है यदि इसका रेखा ग्राफ अच्छी तरह से ढका हुआ है। अधिक दृढ़ता से इसे यादृच्छिक रूप से मिलान योग्य कहा जाता है यदि प्रत्येक अधिकतम मिलान एक सही मिलान है। केवल जुड़े यादृच्छिक रूप से मिलान योग्य ग्राफ पूर्ण ग्राफ और संतुलित पूर्ण द्विदलीय ग्राफ हैं। यह परीक्षण करना संभव है कि क्या एक रेखा ग्राफ, या अधिक सामान्य रूप से एक पंजे-मुक्त ग्राफ, बहुपद समय में अच्छी तरह से कवर किया गया है। पाँच या अधिक परिधि वाले अच्छी तरह से ढके हुए ग्राफों के लक्षण वर्णन, और अच्छी तरह से ढके हुए ग्राफ जो 3-नियमित हैं, भी इन ग्राफों को पहचानने के लिए कुशल बहुपद समय एल्गोरिदम की ओर ले जाते हैं। टिप्पणियाँ संदर्भ। .. जैसा कि उद्धृत किया गया है। .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. जैसा कि उद्धृत किया गया है। .. .. .. ग्राफ परिवार