क्लिक-चौड़ाई

From Vigyanwiki
असंयुक्त संघों, रीलेबलिंग और लेबल-जॉइन्स द्वारा क्लिक-विड्थ 3 के दूरी-वंशानुगत ग्राफ का निर्माण। वर्टेक्स लेबल को रंगों के रूप में दिखाया गया है।

ग्राफ़ सिद्धांत में, ग्राफ़ की क्लिक-विड्थ (क्लिक-विड्थ) (अलग गणित) G एक पैरामीटर है जो ग्राफ़ की संरचनात्मक सम्मिश्रता का वर्णन करता है; इसका ट्री विड्थ से गहरा संबंध है, लेकिन ट्रीविड्थ के विपरीत यह घने ग्राफ़ के लिए छोटा हो सकता है।

इसे निर्माण के लिए आवश्यक ग्राफ़ लेबलिंग की न्यूनतम संख्या के रूप में परिभाषित किया गया है G निम्नलिखित 4 ऑपरेशनों के माध्यम से:

  1. नए शिखर का निर्माण v लेबल के साथ i (द्वारा चिह्नित i(v))
  2. दो लेबल वाले ग्राफ़ के ग्राफ़ का असंयुक्त संघ G और H (द्वारा चिह्नित )
  3. लेबल वाले प्रत्येक शीर्ष पर एक किनारे से जुड़ना i लेबल किए गए प्रत्येक शीर्ष पर j (द्वारा चिह्नित η(i,j)), जहाँ ij
  4. लेबल का नाम बदलना i सूचक पत्र के लिए j (द्वारा चिह्नित ρ(i,j))

बंधे हुए क्लिक-विड्थ के ग्राफ़ में कॉग्रफ़ और दूरी-वंशानुगत ग्राफ़ सम्मिलित हैं। यद्यपि क्लिक-विड्थ की गणना करना एनपी-कठिन है जब यह असंबद्ध है, और यह अज्ञात है कि क्या इसे बहुपद समय में गणना की जा सकती है जब यह घिरा हुआ है, क्लिक-विड्थ के लिए कुशल सन्निकटन एल्गोरिदम ज्ञात हैं। इन एल्गोरिदम और कौरसेल के प्रमेय के आधार पर, कई ग्राफ़ अनुकूलन समस्याएं जो यादृच्छिक ग्राफ़ के लिए एनपी कठिन (NP-hard) हैं, उन्हें बाउंडेड क्लिक-विड्थ के ग्राफ़ पर जल्दी से हल या अनुमानित किया जा सकता है।

क्लिक-विड्थ की अवधारणा के अंतर्निहित निर्माण क्रम को 1990 में ब्रूनो कौरसेल, एंगेलफ्रिएट और रोज़ेनबर्ग द्वारा तैयार किया गया था।[1] और तक Wanke (1994). क्लिक-विड्थ नाम का उपयोग एक अलग अवधारणा के लिए किया गया था Chlebíková (1992). 1993 तक, इस शब्द का वर्तमान अर्थ पहले से ही उपस्थित था।[2]

ग्राफ़ के विशेष वर्ग

कॉग्राफ वास्तव में अधिकतम 2 क्लिक-विड्थ वाले ग्राफ़ होते हैं।[3] प्रत्येक दूरी-वंशानुगत ग्राफ़ में अधिकतम 3 क्लिक-विड्थ होती है। हालाँकि, इकाई अंतराल ग्राफ़ की क्लिक-विड्थ असीमित होती है (उनकी ग्रिड संरचना के आधार पर)।[4] इसी प्रकार, द्विदलीय क्रमपरिवर्तन ग्राफ़ की क्लिक-विड्थ असीमित है (समान ग्रिड संरचना के आधार पर)।[5] चार शीर्षों वाले पथ के लिए बिना किसी प्रेरित सबग्राफ आइसोमोर्फिक वाले ग्राफ़ के रूप में कोग्राफ के लक्षण वर्णन के आधार पर, निषिद्ध प्रेरित सबग्राफ द्वारा परिभाषित कई ग्राफ वर्गों की क्लिक-विड्थ को वर्गीकृत किया गया है।[6]

बंधे हुए क्लिक-विड्थ वाले अन्य ग्राफ़ में लीफ पावर सम्मिलित है; k-परिबद्ध मूल्यों के लिए लीफ पावर्स k; ये एक पेड़ की पत्तियों के प्रेरित उपसमूह हैं T ग्राफ शक्ति में Tk. हालाँकि, असीमित घातांक वाली पत्ती शक्तियों में सीमित क्लिक-विड्थ नहीं होती है।[7]

सीमा

Courcelle & Olariu (2000) और Corneil & Rotics (2005) कुछ ग्राफ़ की क्लिक-विड्थ पर निम्नलिखित सीमाएँ साबित हुईं:

  • यदि किसी ग्राफ़ में अधिकतम क्लिक-विड्थ है k, तो ग्राफ़ का प्रत्येक प्रेरित सबग्राफ भी ऐसा ही करता है।[8]
  • क्लिक-विड्थ के ग्राफ का पूरक ग्राफ k में अधिकतम क्लिक-विड्थ है 2k.[9]
  • ट्रीविड्थ के रेखांकन w अधिकतम क्लिक-विड्थ है 3 · 2w − 1. इस सीमा में घातीय निर्भरता आवश्यक है: ऐसे ग्राफ़ उपस्थित हैं जिनकी क्लिक-विड्थ उनकी ट्रीविड्थ से तेजी से बड़ी है।[10] दूसरी दिशा में, परिबद्ध क्लिक-विड्थ के ग्राफ़ में असीमित ट्रीविड्थ हो सकती है; उदाहरण के लिए, n-वर्टेक्स पूर्ण ग्राफ़ में क्लिक-विड्थ 2 लेकिन ट्रीविड्थ है n − 1. हालाँकि, क्लिक-विड्थ के ग्राफ़ k जिसका कोई पूर्ण द्विदलीय ग्राफ़ नहीं है Kt,t एक सबग्राफ के रूप में अधिकतम ट्रीविड्थ है 3k(t − 1) − 1. इसलिए, विरल ग्राफ़ के प्रत्येक विड्थ के लिए, परिबद्ध ट्रीविड्थ परिबद्ध क्लिक-विड्थ के बराबर है।[11]
  • एक अन्य ग्राफ़ पैरामीटर, रैंक-विड्थ, क्लिक-विड्थ द्वारा दोनों दिशाओं में घिरा हुआ है: rank-width ≤ clique-width ≤ 2rank-width + 1.[12]

इसके अतिरिक्त, यदि कोई ग्राफ G में क्लिक-विड्थ है k, फिर ग्राफ पावर Gc में अधिकतम क्लिक-विड्थ है 2kck.[13] हालाँकि ट्रीविड्थ से क्लिक-विड्थ की सीमा और ग्राफ़ शक्तियों की क्लिक-विड्थ की सीमा दोनों में एक घातीय अंतर है, ये सीमाएँ एक-दूसरे को संयोजित नहीं करती हैं:

यदि एक ग्राफ G में ट्रीविड्थ है w, तब Gc में अधिकतम क्लिक-विड्थ है 2(c + 1)w + 1 − 2, ट्रीविड्थ में केवल एकल घातीय।[14]

कम्प्यूटेशनल सम्मिश्रता

कई अनुकूलन समस्याएं जो ग्राफ़ के अधिक सामान्य वर्गों के लिए एनपी-हार्ड हैं, उन्हें बंधे हुए क्लिक-विड्थ के ग्राफ़ पर गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है, जब इन ग्राफ़ के लिए एक निर्माण अनुक्रम ज्ञात होता है।[15][16] विशेष रूप से, प्रत्येक ग्राफ़ संपत्ति जिसे एमएसओ में व्यक्त किया जा सकता है1 मोनैडिक द्वितीय-क्रम तर्क (तर्क का एक रूप जो शीर्षों के सेट पर परिमाणीकरण की अनुमति देता है) में कौरसेल के प्रमेय के एक रूप के अनुसार, बंधे हुए क्लिक-विड्थ के ग्राफ़ के लिए एक रैखिक-समय एल्गोरिदम है।[16]

बहुपद समय में बंधे हुए क्लिक-विड्थ के ग्राफ़ के लिए इष्टतम ग्राफ़ रंग या हैमिल्टनियन चक्र ढूंढना भी संभव है, जब एक निर्माण अनुक्रम ज्ञात होता है, लेकिन बहुपद का घातांक क्लिक-विड्थ के साथ बढ़ता है, और कम्प्यूटेशनल सम्मिश्रता सिद्धांत से साक्ष्य से पता चलता है कि यह निर्भरता आवश्यक होने की संभावना है।[17] परिबद्ध क्लिक-विड्थ के ग्राफ χ-परिबद्ध| हैंχ-बाउंडेड, जिसका अर्थ है कि उनकी रंगीन संख्या उनके सबसे बड़े समूह के आकार का एक कार्य है।[18]

विभाजित अपघटन पर आधारित एल्गोरिदम का उपयोग करके बहुपद समय में क्लिक-विड्थ तीन के ग्राफ़ को पहचाना जा सकता है, और उनके लिए एक निर्माण अनुक्रम पाया जा सकता है।[19] असंबद्ध क्लिक-विड्थ के ग्राफ़ के लिए, क्लिक-विड्थ की सटीक गणना करना एनपी-कठिन है, और सबलाइनर एडिटिव त्रुटि के साथ एक अनुमान प्राप्त करना भी एनपी-कठिन है।[20] हालाँकि, जब क्लिक-विड्थ बंधी होती है, तो बहुपद समय में बंधी हुई विड्थ (वास्तविक क्लिक-विड्थ से तेजी से बड़ी) का निर्माण अनुक्रम प्राप्त करना संभव है,[21] विशेष रूप से शीर्षों की संख्या में द्विघात समय में।[22] यह खुला रहता है कि क्या सटीक क्लिक-विड्थ, या इसके लिए एक सख्त सन्निकटन, की गणना पैरामीटरयुक्त सम्मिश्रता में की जा सकती है।[20]

संबंधित विड्थ पैरामीटर

बाउंडेड क्लिक-विड्थ के ग्राफ़ का सिद्धांत बाउंडेड ट्रीविड्थ के ग्राफ़ के समान है, लेकिन ट्रीविड्थ के विपरीत घने ग्राफ़ की अनुमति देता है। यदि ग्राफ़ के एक विड्थ ने क्लिक-विड्थ को सीमित कर दिया है, तो या तो इसमें ट्रीविड्थ की सीमा है या प्रत्येक पूर्ण द्विदलीय ग्राफ विड्थ में एक ग्राफ का एक उपग्राफ है।[11] ट्रीविड्थ और क्लिक-विड्थ भी लाइन ग्राफ़ के सिद्धांत के माध्यम से जुड़े हुए हैं: ग्राफ़ के एक विड्थ ने ट्रीविड्थ को सीमित कर दिया है यदि और केवल यदि उनके लाइन ग्राफ़ ने क्लिक-विड्थ को सीमित कर दिया है।[23]

परिबद्ध क्लिक-विड्थ के ग्राफ़ में परिबद्ध ट्विन-विड्थ भी होती है।[24]

टिप्पणियाँ


संदर्भ