कोग्राफ

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

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

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

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

परिभाषा

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

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

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

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

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

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

• कोग्राफ एक ग्राफ है जिसमें पथ (ग्राफ सिद्धांत) P₄ सम्मिलित नहीं है प्रेरित सबग्राफ (ग्राफ जिसके सभी बिंदु और रेखाएं एक बड़े ग्राफ में व्यवस्थित हैं) के रूप में 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 क्लिक-चौड़ाई वाला ग्राफ है।
• कोग्राफ श्रृंखला-समानांतर आंशिक क्रम का तुलनात्मक ग्राफ है।
• कोग्राफ वियोज्य क्रमचय का क्रमचय ग्राफ है।
• कोग्राफ एक ग्राफ है जिसकी सभी न्यूनतम कॉर्डल पूर्णता सामान्य प्रकार से पूर्ण ग्राफ हैं।
• कोग्राफ परंपरागत रूप से सही ढंग से रंगा हुआ ग्राफ है, ग्राफ ऐसा है की सभी प्रेरित सबग्राफ का सभी ग्रीडी (लोलुप) रंग रंगों की इष्टतम संख्या का उपयोग करता है।
• ग्राफ कोग्राफ है यदि ग्राफ का प्रत्येक शीर्ष क्रम पूर्ण प्रकार से ऑर्डर करने योग्य ग्राफ है, क्योंकि कोई P₄नहीं है इसका अर्थ है कि किसी भी शीर्ष क्रम में पूर्ण क्रम में कोई बाधा उपस्थित नहीं होगी।

कोट्री

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

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

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

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

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

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

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

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

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

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

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

गणना

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

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ...(ओइआईसी में अनुक्रम A000669)

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

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

उपवर्ग

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

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

सुपरक्लास

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

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

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

संदर्भ

• 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