कोग्राफ

तुरान ग्राफ टी(13,4), एक कोग्राफ का एक उदाहरण

ग्राफ सिद्धांत में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या पी₄मुक्त ग्राफ़, ग्राफ़ (असतत गणित) है जो एकल-शीर्ष ग्राफ K1 से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K1 सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।

1970 के दशक के बाद से कई लेखकों द्वारा कोग्राफ खोजे गए हैं; प्रारंभिक संदर्भों में युं(1978), , Seinsche (1974), और Sumner (1974). उन्हें डी*-ग्राफ भी कहा गया है, वंशानुगत डेसी ग्राफ (ऑर्थोमॉड्यूलर जाली पर जेम्स सी. डेसी जूनियर के संबंधित कार्य के बाद), और 2-समतुल्यता ग्राफ है। उनके पास सरल संरचनात्मक अपघटन है जिसमें असंयुक्त समूह और पूर्ण ग्राफ संचालन सम्मिलित हैं जिन्हें अंकित किये गए पेड़ द्वारा संक्षिप्त प्रकार से प्रदर्शित किया जा सकता है, और एल्गोरिदमिक रूप से कई समस्याओं को कुशलतापूर्वक सिद्ध करने के लिए उपयोग किया जाता है जैसे कि से अत्यधिक से अत्यधिक सामान्य ग्राफ वर्गों पर कठिन अधिकतम क्लिक ढूंढना है।

कॉग्राफ के विशेष कारणों में पूर्ण ग्राफ़, द्विपक्षीय ग्राफ, क्लस्टर ग्राफ, और ग्राफ शामिल हैं। कॉग्राफ बदले में, दूरी-वंशानुगत ग्राफ, क्रमचय ग्राफ, तुलनात्मक ग्राफ और सही ग्राफ के विशेष मामले हैं।

परिभाषा

पुनरावर्ती निर्माण

निम्नलिखित नियमों का उपयोग करके किसी भी कोग्राफ का निर्माण किया जा सकता है:

1. कोई एकल वर्टेक्स ग्राफ एक कोग्राफ है;
2. अगर $G$ एक कॉग्राफ है, इसलिए इसका पूरक ग्राफ है ${\overline {G}}$;
3. अगर $G$ और $H$ cographs हैं, इसलिए उनका असम्बद्ध संघ है $G\cup H$.

कॉग्राफ को उन ग्राफ़ के रूप में परिभाषित किया जा सकता है, जो एकल-वर्टेक्स ग्राफ़ से शुरू होकर इन ऑपरेशनों का उपयोग करके बनाए जा सकते हैं। वैकल्पिक रूप से, पूरक ऑपरेशन का उपयोग करने के बजाय, ज्वाइन ऑपरेशन का उपयोग किया जा सकता है, जो असंयुक्त संघ बनाने के होते हैं $G\cup H$ और फिर एक शीर्ष के प्रत्येक जोड़े के बीच एक किनारे को जोड़ना $G$ और एक शीर्ष से $H$.

अन्य विशेषताएं

कॉग्राफ के कई वैकल्पिक लक्षण वर्णन दिए जा सकते हैं। उनमें से:

• एक कोग्राफ एक ग्राफ है जिसमें पथ (ग्राफ सिद्धांत) पी शामिल नहीं है₄ एक प्रेरित सबग्राफ के रूप में 4 शीर्षों पर (और इसलिए लंबाई 3)। यही है, एक ग्राफ एक कॉग्राफ है अगर और केवल अगर किसी भी चार कोने के लिए $v_{1},v_{2},v_{3},v_{4}$, अगर $\{v_{1},v_{2}\},\{v_{2},v_{3}\}$ और $\{v_{3},v_{4}\}$ ग्राफ के किनारे हैं तो कम से कम एक $\{v_{1},v_{3}\},\{v_{1},v_{4}\}$ या $\{v_{2},v_{4}\}$ किनारा भी है।
• एक कोग्राफ एक ग्राफ है जिसके सभी प्रेरित सबग्राफ में यह गुण होता है कि कोई भी अधिकतम क्लिक (ग्राफ सिद्धांत) किसी एकल शीर्ष में किसी भी अधिकतम स्वतंत्र सेट को काटता है।
• एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक गैर-तुच्छ प्रेरित सबग्राफ में समान पड़ोस के साथ कम से कम दो शिखर होते हैं।
• एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक जुड़े प्रेरित सबग्राफ में एक डिस्कनेक्ट पूरक होता है।
• एक कोग्राफ एक ग्राफ है जिसके सभी जुड़े प्रेरित सबग्राफ में दूरी (ग्राफ सिद्धांत) अधिकतम 2 है।
• एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक जुड़ा हुआ घटक (ग्राफ सिद्धांत) अधिकतम 2 व्यास वाला एक दूरी-वंशानुगत ग्राफ है।
• एक कोग्राफ अधिकतम 2 क्लिक-चौड़ाई वाला एक ग्राफ है।
• एक कोग्राफ एक श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है।
• एक कोग्राफ एक वियोज्य क्रमचय का क्रमचय ग्राफ है।
• एक कोग्राफ एक ग्राफ है जिसकी सभी न्यूनतम कॉर्डल पूर्णता तुच्छ रूप से पूर्ण ग्राफ हैं।
• एक कॉग्राफ एक वंशानुगत संपत्ति है ग्रंडी संख्या | अच्छी तरह से रंगीन ग्राफ, एक ग्राफ ऐसा है कि प्रत्येक प्रेरित सबग्राफ के प्रत्येक लालची रंग में रंगों की एक इष्टतम संख्या का उपयोग होता है।
• एक ग्राफ एक कोग्राफ है अगर और केवल अगर ग्राफ का प्रत्येक शीर्ष क्रम एक पूरी तरह से ऑर्डर करने योग्य ग्राफ है, क्योंकि कोई पी नहीं है₄ इसका मतलब है कि किसी भी शीर्ष क्रम में एक पूर्ण क्रम में कोई बाधा मौजूद नहीं होगी।

कोट्री

एक कॉट्री और संबंधित कोग्राफ। कॉग्राफ में प्रत्येक किनारे (यू, वी) में कॉट्री में यू और वी के कम से कम आम पूर्वज के लिए एक मिलान रंग होता है।

एक कोट्री एक पेड़ है जिसमें आंतरिक नोड्स को 0 और 1 की संख्या के साथ लेबल किया जाता है। प्रत्येक कॉट्री टी एक कोग्राफ जी को परिभाषित करता है जिसमें टी की पत्तियां शीर्ष के रूप में होती हैं, और जिसमें 'टी' के प्रत्येक नोड पर निहित सबट्री उस नोड से नीचे उतरने वाले पत्तों के सेट द्वारा परिभाषित जी में प्रेरित सबग्राफ से मेल खाती है:

• सिंगल लीफ नोड वाला एक सबट्री एक सिंगल वर्टेक्स के साथ एक प्रेरित सबग्राफ से मेल खाता है।
• 0 लेबल वाले नोड पर रूट किया गया सबट्री उस नोड के चिल्ड्रन द्वारा परिभाषित सबग्राफ के मिलन से मेल खाता है।
• 1 लेबल वाले नोड पर रूट किया गया सबट्री उस नोड के चिल्ड्रन द्वारा परिभाषित सबग्राफ के जॉइन से मेल खाता है; अर्थात्, हम संघ बनाते हैं और विभिन्न उपवृक्षों में पत्तियों के संगत प्रत्येक दो शीर्षों के बीच एक किनारा जोड़ते हैं। वैकल्पिक रूप से, ग्राफ़ के एक सेट के जुड़ाव को प्रत्येक ग्राफ़ के पूरक के रूप में देखा जा सकता है, पूरक के संघ का गठन किया जा सकता है, और फिर परिणामी संघ को पूरक बनाया जा सकता है।

कोट्री से बने कॉग्राफ का वर्णन करने का एक समतुल्य तरीका यह है कि दो कोने एक किनारे से जुड़े होते हैं यदि और केवल अगर संबंधित पत्तियों के सबसे कम सामान्य पूर्वज को 1 द्वारा लेबल किया जाता है। इसके विपरीत, प्रत्येक कोट्री द्वारा इस तरह से प्रतिनिधित्व किया जा सकता है . यदि हमें 0 और 1 के बीच वैकल्पिक करने के लिए इस पेड़ के किसी रूट-लीफ पथ पर लेबल की आवश्यकता है, तो यह प्रतिनिधित्व अद्वितीय है।

कम्प्यूटेशनल गुण

कोग्राफ को रैखिक समय में पहचाना जा सकता है, और मॉड्यूलर अपघटन का उपयोग करके एक कॉट्री प्रतिनिधित्व का निर्माण किया जा सकता है, विभाजन शोधन, लेक्सबीएफएस , या विभाजित अपघटन। एक बार कोट्री प्रतिनिधित्व का निर्माण हो जाने के बाद, कई परिचित ग्राफ़ समस्याओं को कॉट्रीज़ पर सरल बॉटम-अप गणनाओं के माध्यम से हल किया जा सकता है।

उदाहरण के लिए, एक कोग्राफ में क्लिक समस्या को खोजने के लिए, नीचे-ऊपर के क्रम में प्रत्येक सबग्राफ में अधिकतम क्लिक कोट्री के सबट्री द्वारा दर्शाया गया है। 0 लेबल वाले नोड के लिए, उस नोड के बच्चों के लिए गणना की गई क्लिक्स में अधिकतम क्लिक अधिकतम है। 1 लेबल वाले नोड के लिए, अधिकतम क्लिक उस नोड के बच्चों के लिए गणना की गई क्लिक्स का संघ है, और इसका आकार बच्चों के क्लिक आकार के योग के बराबर है। इस प्रकार, कोट्री के प्रत्येक नोड पर संग्रहीत मूल्यों को वैकल्पिक रूप से अधिकतम और योग करके, हम अधिकतम क्लिक आकार की गणना कर सकते हैं, और वैकल्पिक रूप से अधिकतम और यूनियनों को लेकर, हम अधिकतम क्लिक का निर्माण कर सकते हैं। समान बॉटम-अप ट्री कम्प्यूटेशंस मैक्सिमल इंडिपेंडेंट सेट, ग्राफ रंगना , मैक्सिमम क्लिक कवर, और हैमिल्टनिसिटी (जो कि हैमिल्टनियन पथ समस्या का अस्तित्व है) को कोग्राफ के कॉट्री प्रतिनिधित्व से रैखिक समय में गणना करने की अनुमति देता है। क्योंकि कोग्राफ ने क्लिक-चौड़ाई को सीमित कर दिया है, कौरसेल के प्रमेय का उपयोग ग्राफ़ के मोनाडिक सेकंड-ऑर्डर लॉजिक (MSO) में किसी भी संपत्ति का परीक्षण करने के लिए किया जा सकता है।₁) रैखिक समय में कोग्राफ पर।

यह परीक्षण करने की समस्या है कि क्या दिया गया ग्राफ k वर्टिकल दूर है और/या टी किनारों को एक कोग्राफ से दूर है, पैरामीटरयुक्त जटिलता | निश्चित-पैरामीटर ट्रैक्टेबल है। यह तय करना कि क्या ग्राफ को कोग्राफ में k-एज-डिलीट किया जा सकता है, O में हल किया जा सकता है^*(2.415^{कश्मीर}) समय, और k-एज-संपादित O में एक cograph के लिए^*(4.612^{के </सुप>). यदि किसी ग्राफ का सबसे बड़ा प्रेरित कोग्राफ सबग्राफ ग्राफ से k कोने को हटाकर पाया जा सकता है, तो इसे O में पाया जा सकता है*(3.30कश्मीर) समय।}

दो कॉग्राफ ग्राफ समरूपता हैं यदि और केवल यदि उनके सहपत्र (कैनोनिकल रूप में एक ही लेबल के साथ दो आसन्न कोने नहीं हैं) समरूपी हैं। इस तुल्यता के कारण, एक रैखिक समय में यह निर्धारित कर सकता है कि क्या दो कोग्राफ आइसोमोर्फिक हैं, उनके कॉट्रीज़ का निर्माण करके और लेबल किए गए पेड़ों के लिए एक रैखिक समय समरूपता परीक्षण लागू करना।

यदि एच एक कोग्राफ जी का प्रेरित सबग्राफ है, तो एच स्वयं एक कोग्राफ है; जी के लिए कोट्री से कुछ पत्तियों को हटाकर एच के लिए कॉट्री का गठन किया जा सकता है और फिर केवल एक बच्चे वाले नोड्स को दबा दिया जा सकता है। क्रुस्कल के वृक्ष प्रमेय से यह अनुसरण करता है कि एक प्रेरित सबग्राफ होने का द्विआधारी संबंध कॉग्राफ पर एक अच्छी तरह से अर्ध-आदेश है। इस प्रकार, यदि कॉग्राफ की एक सबफ़ैमिली (जैसे प्लेनर ग्राफ ़ कोग्राफ़) को प्रेरित सबग्राफ़ ऑपरेशंस के तहत बंद कर दिया जाता है, तो उसके पास निषिद्ध ग्राफ़ लक्षण वर्णन की एक सीमित संख्या होती है। कम्प्यूटेशनल रूप से, इसका मतलब यह है कि इस तरह के सबफ़ैमिली में सदस्यता का परीक्षण रैखिक समय में किया जा सकता है, यह परीक्षण करने के लिए दिए गए ग्राफ़ के कॉट्री पर नीचे-ऊपर की गणना का उपयोग करके यह परीक्षण किया जा सकता है कि इसमें इनमें से कोई भी वर्जित उप-अनुच्छेद शामिल है या नहीं। हालाँकि, जब दो कोग्राफ के आकार दोनों परिवर्तनशील होते हैं, तो यह परीक्षण करना कि क्या उनमें से एक दूसरे का एक प्रेरित सबग्राफ है, एनपी-पूर्ण है।

एक बार पढ़ने वाले कार्यों को पहचानने के लिए एल्गोरिदम में कॉग्राफ एक महत्वपूर्ण भूमिका निभाते हैं।

गणना

n = 1, 2, 3, ... के लिए, n शीर्षों के साथ जुड़े कोग्राफ की संख्या है:

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (sequence A000669 in the OEIS)

एन> 1 के लिए डिस्कनेक्ट किए गए कोग्राफ की समान संख्या होती है, क्योंकि प्रत्येक कॉग्राफ के लिए इसका एक या इसका पूरक ग्राफ जुड़ा होता है।

संबंधित ग्राफ परिवार

उपवर्ग

हर पूरा ग्राफ K_n एक कोट्री है, जिसमें एक कॉट्री है जिसमें एक एकल 1-नोड और है n पत्तियाँ। इसी तरह, प्रत्येक पूर्ण द्विदलीय ग्राफ K_a,b एक कोग्राफ है। इसका कॉट्री 1-नोड पर निहित है जिसमें दो 0-नोड बच्चे हैं, एक के साथ a पत्ते वाले बच्चे और एक साथ b पत्ते बच्चे। समान आकार के स्वतंत्र सेटों के एक परिवार के शामिल होने से तुरान ग्राफ बन सकता है; इस प्रकार, यह एक कोट्री भी है, जिसमें 1-नोड पर निहित एक कोट्री है जिसमें प्रत्येक स्वतंत्र सेट के लिए एक बच्चा 0-नोड है।

हर दहलीज का ग्राफ भी एक कॉग्राफ है। एक शीर्ष को बार-बार जोड़कर एक दहलीज ग्राफ बनाया जा सकता है, जो या तो पिछले सभी शीर्षों से जुड़ा हो या उनमें से कोई भी न हो; ऐसा प्रत्येक ऑपरेशन असंयुक्त संघ में से एक है या संचालन में शामिल होता है जिसके द्वारा एक कॉट्री बन सकता है।

सुपरक्लास

संपत्ति द्वारा कॉग्राफ का लक्षण वर्णन कि प्रत्येक क्लिक और अधिकतम स्वतंत्र सेट में एक गैर-रिक्त चौराहा होता है, दृढ़ता से परिपूर्ण रेखांकन की परिभाषित संपत्ति का एक मजबूत संस्करण होता है, जिसमें प्रत्येक प्रेरित सबग्राफ में एक स्वतंत्र सेट होता है जो सभी अधिकतम समूहों को काटता है। एक कोग्राफ में, प्रत्येक अधिकतम स्वतंत्र सेट सभी अधिकतम समूहों को काटता है। इस प्रकार, प्रत्येक कोग्राफ दृढ़ता से परिपूर्ण है।

तथ्य यह है कि कॉग्राफ पी हैं₄-फ्री का तात्पर्य है कि वे पूरी तरह से ऑर्डर करने योग्य ग्राफ हैं। वास्तव में, एक कोग्राफ का प्रत्येक शीर्ष क्रम एक सही क्रम है, जिसका अर्थ है कि अधिकतम क्लिक खोज और न्यूनतम रंग किसी भी लालची रंग के साथ रैखिक समय में पाया जा सकता है और कोट्री अपघटन की आवश्यकता के बिना।

प्रत्येक कॉग्राफ एक दूरी-वंशानुगत ग्राफ है, जिसका अर्थ है कि कॉग्राफ में प्रत्येक प्रेरित पथ सबसे छोटा पथ है। कोग्राफ को दूरी-वंशानुगत ग्राफ के बीच प्रत्येक जुड़े हुए घटक में व्यास दो के रूप में चित्रित किया जा सकता है। प्रत्येक कोग्राफ भी एक श्रृंखला-समानांतर आंशिक क्रम का एक तुलनात्मक ग्राफ है, जो अलग-अलग संघ को बदलकर प्राप्त किया जाता है और संचालन में शामिल होता है जिसके द्वारा कोग्राफ को अलग-अलग संघ और आंशिक आदेशों पर क्रमिक योग संचालन द्वारा बनाया गया था। क्योंकि दृढ़ता से सही रेखांकन, पूरी तरह से क्रमबद्ध रेखांकन, दूरी-वंशानुगत रेखांकन, और तुलनीय रेखांकन सभी सही रेखांकन हैं, कॉग्राफ भी परिपूर्ण हैं।

संदर्भ

• Berge, C.; Duchet, P. (1984), "Strongly perfect graphs", Topics on Perfect Graphs, North-Holland Mathematics Studies, vol. 88, Amsterdam: North-Holland, pp. 57–61, doi:10.1016/S0304-0208(08)72922-0, MR 0778749.
• Bose, Prosenjit; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters, 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3, MR 1620935.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6.
• Burlet, M.; Uhry, J. P. (1984), "Parity Graphs", Topics on Perfect Graphs, Annals of Discrete Mathematics, vol. 21, pp. 253–277.
• Bretscher, A.; Corneil, D. G.; Habib, M.; Paul, C. (2008), "A simple Linear Time LexBFS Cograph Recognition Algorithm", SIAM Journal on Discrete Mathematics, 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016, doi:10.1137/060664690.
• Cai, L. (1996), "Fixed-parameter tractability of graph modification problems for hereditary properties", Information Processing Letters, 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6.
• Christen, Claude A.; Selkow, Stanley M. (1979), "Some perfect coloring properties of graphs", Journal of Combinatorial Theory, Series B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, MR 0539075.
• Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics, 3 (3): 163–174, doi:10.1016/0166-218X(81)90013-5, MR 0619603.
• Corneil, D. G.; Perl, Y.; Stewart, L. K. (1985), "A linear recognition algorithm for cographs", SIAM Journal on Computing, 14 (4): 926–934, doi:10.1137/0214065, MR 0807891.
• Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs of bounded clique-width", Theory of Computing Systems, 33 (2): 125–150, doi:10.1007/s002249910009, MR 1739644, S2CID 15402031, Zbl 1009.68102.
• Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics, 101 (1–3): 77–144, doi:10.1016/S0166-218X(99)00184-5, MR 1743732.
• Damaschke, Peter (1990), "Induced subgraphs and well-quasi-ordering", Journal of Graph Theory, 14 (4): 427–435, doi:10.1002/jgt.3190140406, MR 1067237.
• Damaschke, Peter (1991), "Induced subraph isomorphism for cographs is NP-complete", in Möhring, Rolf H. (ed.), Graph-Theoretic Concepts in Computer Science: 16th International Workshop WG '90 Berlin, Germany, June 20–22, 1990, Proceedings, Lecture Notes in Computer Science, vol. 484, Springer-Verlag, pp. 72–78, doi:10.1007/3-540-53832-1_32.
• Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016/j.dam.2011.05.007, MR 2901084, S2CID 6528410.
• Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439.

• Habib, Michel; Paul, Christophe (2005), "A simple linear time algorithm for cograph recognition" (PDF), Discrete Applied Mathematics, 145 (2): 183–197, doi:10.1016/j.dam.2004.01.011, MR 2113140.
• Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
• Lerchs, H. (1971), On cliques and kernels, Tech. Report, Dept. of Comp. Sci., Univ. of Toronto.
• Liu, Yunlong Liu; Wang, Jianxin; Guo, Jiong; Chen, Jianer (2012), "Complexity and parameterized algorithms for Cograph Editing", Theoretical Computer Science, 461: 45–54, doi:10.1016/j.tcs.2011.11.040.
• Nastos, James; Gao, Yong (2010), "A novel branching strategy for parameterized graph modification problems", in Wu, Weili; Daescu, Ovidiu (eds.), Combinatorial Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18–20, 2010, Proceedings, Part II, Lecture Notes in Computer Science, vol. 6509, Springer, pp. 332–346, arXiv:1006.3020, doi:10.1007/978-3-642-17461-2_27
• Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", 4th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Discrete Applied Mathematics, 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR 1478250.
• Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B, 16 (2): 191–193, doi:10.1016/0095-8956(74)90063-X, MR 0337679.
• Sumner, D. P. (1974), "Dacey graphs", Journal of the Australian Mathematical Society, 18 (4): 492–502, doi:10.1017/S1446788700029232, MR 0382082.

बाहरी संबंध

• "Cograph graphs", Information System on Graph Class Inclusions
• Weisstein, Eric W., "Cograph", MathWorld