कोग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(34 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Short description|Graph formed by complementation and disjoint union}}
{{Short description|Graph formed by complementation and disjoint union}}
[[File:Turan 13-4.svg|thumb|तुरान ग्राफ टी(13,4), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या ''पी''<sub>4</sub>मुक्त ग्राफ़, ग्राफ़ (असतत गणित) है जिसे सिंगल-वर्टेक्स ग्राफ़ ''K'' से उत्पन्न किया जा सकता है<sub>1</sub> [[पूरक ग्राफ]] द्वारा और रेखांकन के संघ को अलग करना। अर्थात्, कॉग्राफ का परिवार ग्राफ़ का सबसे छोटा वर्ग है जिसमें K शामिल है<sub>1</sub> और पूरक और असम्बद्ध संघ के तहत बंद है।
[[File:Turan 13-4.svg|thumb|तुरान ग्राफ टी (13,4), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, '''कोग्राफ''', कम करने योग्य पूरक ग्राफ, या P<sub>4</sub> स्वतंत्र  ग्राफ़ है, ग्राफ़ (असतत गणित) जो एकल-शीर्ष ग्राफ K<sub>1</sub> से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K<sub>1</sub> सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।  


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


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


== परिभाषा ==
== परिभाषा ==
Line 11: Line 10:
=== पुनरावर्ती निर्माण ===
=== पुनरावर्ती निर्माण ===
निम्नलिखित नियमों का उपयोग करके किसी भी कोग्राफ का निर्माण किया जा सकता है:
निम्नलिखित नियमों का उपयोग करके किसी भी कोग्राफ का निर्माण किया जा सकता है:
# कोई एकल वर्टेक्स ग्राफ एक कोग्राफ है;
# कोई एकल शीर्ष ग्राफ कोग्राफ है;
# अगर <math>G</math> एक कॉग्राफ है, इसलिए इसका पूरक ग्राफ है <math>\overline{G}</math>;
# यदि <math>G</math> कोग्राफ है, इसलिए <math>\overline{G}</math> इसका पूरक ग्राफ है;
# अगर <math>G</math> और <math>H</math> cographs हैं, इसलिए उनका असम्बद्ध संघ है <math>G\cup H</math>.
# यदि <math>G</math> और <math>H</math> कोग्राफ हैं, इसलिए <math>G\cup H</math> उनका असम्बद्ध समूह है .
कॉग्राफ को उन ग्राफ़ के रूप में परिभाषित किया जा सकता है, जो एकल-वर्टेक्स ग्राफ़ से शुरू होकर इन ऑपरेशनों का उपयोग करके बनाए जा सकते हैं।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}}
कोग्राफ को उन ग्राफ़ के रूप में परिभाषित किया जा सकता है, जो एकल-शीर्ष ग्राफ़ से प्रारम्भ होकर इन संचालनों का उपयोग करके बनाए जा सकते हैं।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}} वैकल्पिक रूप से, पूरक संचालन का उपयोग करने के बदले, संचालन में सम्मिलित होने का उपयोग किया जा सकता है, जिसमे असंयुक्त समूह <math>G\cup H</math> का निर्माण होता है और फिर <math>G</math> से शीर्ष और <math>H</math> से शीर्ष के प्रत्येक जोड़े के बिच किनारा जोड़ना है।   
वैकल्पिक रूप से, पूरक ऑपरेशन का उपयोग करने के बजाय, ज्वाइन ऑपरेशन का उपयोग किया जा सकता है, जो
असंयुक्त संघ बनाने के होते हैं <math>G\cup H</math> और फिर एक शीर्ष के प्रत्येक जोड़े के बीच एक किनारे को जोड़ना <math>G</math> और एक शीर्ष से <math>H</math>.


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


* एक कोग्राफ एक ग्राफ है जिसमें [[पथ (ग्राफ सिद्धांत)]] पी शामिल नहीं है<sub>4</sub> एक [[प्रेरित सबग्राफ]] के रूप में 4 शीर्षों पर (और इसलिए लंबाई 3)। यही है, एक ग्राफ एक कॉग्राफ है अगर और केवल अगर किसी भी चार कोने के लिए <math>v_1,v_2,v_3,v_4</math>, अगर <math>\{v_1,v_2\},\{v_2,v_3\}</math> और <math>\{v_3,v_4\}</math> ग्राफ के किनारे हैं तो कम से कम एक <math>\{v_1,v_3\},\{v_1,v_4\}</math> या <math>\{v_2,v_4\}</math> किनारा भी है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}}
* कोग्राफ एक ग्राफ है जिसमें [[पथ (ग्राफ सिद्धांत)]] P<sub>4</sub> सम्मिलित नहीं है [[प्रेरित सबग्राफ]] (ग्राफ जिसके सभी बिंदु और रेखाएं एक बड़े ग्राफ में व्यवस्थित हैं)  के रूप में 4 शीर्षों पर (और इसलिए लंबाई 3) है। वह ग्राफ एक कोग्राफ है यदि किसी भी चार कोने के लिए <math>v_1,v_2,v_3,v_4</math>, यदि <math>\{v_1,v_2\},\{v_2,v_3\}</math> और <math>\{v_3,v_4\}</math> ग्राफ के किनारे हैं तो कम से कम एक <math>\{v_1,v_3\},\{v_1,v_4\}</math> या <math>\{v_2,v_4\}</math> किनारा भी है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}}
* एक कोग्राफ एक ग्राफ है जिसके सभी प्रेरित सबग्राफ में यह गुण होता है कि कोई भी अधिकतम [[क्लिक (ग्राफ सिद्धांत)]] किसी एकल शीर्ष में किसी भी [[अधिकतम स्वतंत्र सेट]] को काटता है।
* कोग्राफ एक ग्राफ है जिसके सभी प्रेरित सबग्राफ में यह गुण होता है कि कोई भी अधिकतम [[क्लिक (ग्राफ सिद्धांत)]] किसी एकल शीर्ष में किसी भी [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समूह]] को काटता है।
* एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक गैर-तुच्छ प्रेरित सबग्राफ में समान पड़ोस के साथ कम से कम दो शिखर होते हैं।
* कोग्राफ एक ग्राफ है जिसमें प्रत्येक असाधारण प्रेरित सबग्राफ में समान समीपत्व के साथ कम से कम दो शिखर होते हैं।
* एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक जुड़े प्रेरित सबग्राफ में एक डिस्कनेक्ट पूरक होता है।
* कोग्राफ एक ग्राफ है जिसमें प्रत्येक जुड़े प्रेरित सबग्राफ में अलग पूरक होता है।
* एक कोग्राफ एक ग्राफ है जिसके सभी जुड़े प्रेरित सबग्राफ में [[दूरी (ग्राफ सिद्धांत)]] अधिकतम 2 है।
*कोग्राफ एक ग्राफ है जिसके सभी जुड़े प्रेरित सबग्राफ में [[दूरी (ग्राफ सिद्धांत)]] अधिकतम 2 है।
* एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक [[जुड़ा हुआ घटक (ग्राफ सिद्धांत)]] अधिकतम 2 व्यास वाला एक दूरी-वंशानुगत ग्राफ है।
* कोग्राफ एक ग्राफ है जिसमें प्रत्येक [[जुड़ा हुआ घटक (ग्राफ सिद्धांत)]] अधिकतम 2 व्यास वाला दूरी-पारम्परिक ग्राफ है।
* एक कोग्राफ अधिकतम 2 क्लिक-चौड़ाई वाला एक ग्राफ है।{{sfnp|Courcelle|Olariu|2000}}
* कोग्राफ अधिकतम 2 क्लिक-चौड़ाई वाला ग्राफ है।{{sfnp|Courcelle|Olariu|2000}}
* एक कोग्राफ एक [[श्रृंखला-समानांतर आंशिक क्रम]] का तुलनात्मक ग्राफ है।{{sfnp|Jung|1978}}
* कोग्राफ [[श्रृंखला-समानांतर आंशिक क्रम]] का तुलनात्मक ग्राफ है।{{sfnp|Jung|1978}}
* एक कोग्राफ एक [[वियोज्य क्रमचय]] का क्रमचय ग्राफ है।{{sfnp|Bose|Buss|Lubiw|1998}}
* कोग्राफ [[वियोज्य क्रमचय]] का क्रमचय ग्राफ है।{{sfnp|Bose|Buss|Lubiw|1998}}
* एक कोग्राफ एक ग्राफ है जिसकी सभी न्यूनतम [[कॉर्डल पूर्णता]] तुच्छ रूप से पूर्ण ग्राफ हैं।{{sfnp|Parra|Scheffler|1997}}
* कोग्राफ एक ग्राफ है जिसकी सभी न्यूनतम [[कॉर्डल पूर्णता]] सामान्य प्रकार से पूर्ण ग्राफ हैं।{{sfnp|Parra|Scheffler|1997}}  
* एक कॉग्राफ एक [[वंशानुगत संपत्ति]] है ग्रंडी संख्या | अच्छी तरह से रंगीन ग्राफ, एक ग्राफ ऐसा है कि प्रत्येक प्रेरित सबग्राफ के प्रत्येक [[लालची रंग]] में रंगों की एक इष्टतम संख्या का उपयोग होता है।{{sfnp|Christen|Selkow|1979}}
* कोग्राफ परंपरागत रूप से सही ढंग से रंगा हुआ ग्राफ है, ग्राफ ऐसा है की सभी प्रेरित सबग्राफ का सभी ग्रीडी (लोलुप) रंग रंगों की इष्टतम संख्या का उपयोग करता है।{{sfnp|Christen|Selkow|1979}}
* एक ग्राफ एक कोग्राफ है अगर और केवल अगर ग्राफ का प्रत्येक शीर्ष क्रम एक पूरी तरह से ऑर्डर करने योग्य ग्राफ है, क्योंकि कोई पी नहीं है<sub>4</sub> इसका मतलब है कि किसी भी शीर्ष क्रम में एक पूर्ण क्रम में कोई बाधा मौजूद नहीं होगी।
* ग्राफ कोग्राफ है यदि ग्राफ का प्रत्येक शीर्ष क्रम पूर्ण प्रकार से ऑर्डर करने योग्य ग्राफ है, क्योंकि कोई P<sub>4</sub>नहीं है इसका अर्थ है कि किसी भी शीर्ष क्रम में पूर्ण क्रम में कोई बाधा उपस्थित नहीं होगी।


== कोट्री ==
== कोट्री ==
[[File:Cotree and cograph.svg|thumb|upright=1.6|एक कॉट्री और संबंधित कोग्राफ। कॉग्राफ में प्रत्येक किनारे (यू, वी) में कॉट्री में यू और वी के कम से कम आम पूर्वज के लिए एक मिलान रंग होता है।]]एक कोट्री एक पेड़ है जिसमें आंतरिक नोड्स को 0 और 1 की संख्या के साथ लेबल किया जाता है। प्रत्येक कॉट्री ''टी'' एक कोग्राफ ''जी'' को परिभाषित करता है जिसमें ''टी'' की पत्तियां शीर्ष के रूप में होती हैं, और जिसमें 'टी' के प्रत्येक नोड पर निहित सबट्री उस नोड से नीचे उतरने वाले पत्तों के सेट द्वारा परिभाषित ''जी'' में प्रेरित सबग्राफ से मेल खाती है:
[[File:Cotree and cograph.svg|thumb|upright=1.6|एक कॉट्री और संबंधित कोग्राफ। कॉग्राफ में प्रत्येक किनारे (u, v) में कॉट्री में u और v के कम से कम आम पूर्वज के लिए एक मिलान रंग होता है।]]कोट्री एक ट्री है जिसका आतंरिक बिंदु को 0 और 1 की संख्या के साथ लेबल किया जाता है। जिसमे सभी कोट्री ''T'' एक कॉग्राफ ''G'' होने को परिभाषित करता है जिसमे की पत्तियां ''T'' शीर्ष के रूप में होती हैं, और ''T'' प्रत्येक बिंदु पर स्थापित उपशीर्षक उस बिंदु से निचे उतरने वाले पत्तों के समूहों द्वारा परिभाषित ''G'' में प्रेरित सबग्राफ के समान होता है;
* सिंगल लीफ नोड वाला एक सबट्री एक सिंगल वर्टेक्स के साथ एक प्रेरित सबग्राफ से मेल खाता है।
* एकल पत्ती बिंदु वाला उपशीर्षक एकल शीर्ष के साथ प्रेरित सबग्राफ के समान होता है।  
* 0 लेबल वाले नोड पर रूट किया गया सबट्री उस नोड के चिल्ड्रन द्वारा परिभाषित सबग्राफ के मिलन से मेल खाता है।
* 0 लेबल वाले बिंदु पर निहित किया गया उपशीर्षक उस बिंदु के अंश द्वारा परिभाषित सबग्राफ के मिलान की प्रक्रिया के समान होता है।
* 1 लेबल वाले नोड पर रूट किया गया सबट्री उस नोड के चिल्ड्रन द्वारा परिभाषित सबग्राफ के ''जॉइन'' से मेल खाता है; अर्थात्, हम संघ बनाते हैं और विभिन्न उपवृक्षों में पत्तियों के संगत प्रत्येक दो शीर्षों के बीच एक किनारा जोड़ते हैं। वैकल्पिक रूप से, ग्राफ़ के एक सेट के जुड़ाव को प्रत्येक ग्राफ़ के पूरक के रूप में देखा जा सकता है, पूरक के संघ का गठन किया जा सकता है, और फिर परिणामी संघ को पूरक बनाया जा सकता है।
* 1 लेबल वाले बिंदु पर निहित किया गया उपशीर्षक उस बिंदु के अंश द्वारा परिभाषित सबग्राफ के जोड़ के समान होता है; अर्थात्, हम समूह बनाते हैं और विभिन्न उपवृक्षों में पत्तियों के संगत प्रत्येक दो शीर्षों के बीच एक किनारा जोड़ते हैं। वैकल्पिक रूप से, ग्राफ़ के समूह के जुड़ाव को प्रत्येक ग्राफ़ के पूरक के रूप में देखा जा सकता है, पूरक के समूह का गठन किया जा सकता है, और फिर परिणामी समूह को पूरक बनाया जा सकता है।
कोट्री से बने कॉग्राफ का वर्णन करने का एक समतुल्य तरीका यह है कि दो कोने एक किनारे से जुड़े होते हैं यदि और केवल अगर संबंधित पत्तियों के [[सबसे कम सामान्य पूर्वज]] को 1 द्वारा लेबल किया जाता है। इसके विपरीत, प्रत्येक कोट्री द्वारा इस तरह से प्रतिनिधित्व किया जा सकता है . यदि हमें 0 और 1 के बीच वैकल्पिक करने के लिए इस पेड़ के किसी रूट-लीफ पथ पर लेबल की आवश्यकता है, तो यह प्रतिनिधित्व अद्वितीय है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}}
कोट्री से बने कोग्राफ का वर्णन करने का समतुल्य प्रकार यह है कि दो कोने एक किनारे से जुड़े होते हैं यदि सिर्फ संबंधित पत्तियों के [[सबसे कम सामान्य पूर्वज|सबसे कम सामान्य]] पीढ़ी को 1 द्वारा लेबल किया जाता है। इसके विपरीत, प्रत्येक कोट्री द्वारा इस प्रकार से प्रतिनिधित्व किया जा सकता है यदि हमें 0 और 1 के बीच वैकल्पिक करने के लिए इस ट्री के किसी मूल-पत्ती पथ पर लेबल की आवश्यकता है, तो यह प्रतिनिधित्व अद्वितीय है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}}


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


कोग्राफ को रैखिक समय में पहचाना जा सकता है, और [[मॉड्यूलर अपघटन]] का उपयोग करके एक कॉट्री प्रतिनिधित्व का निर्माण किया जा सकता है,{{sfnp|Corneil|Perl|Stewart|1985}} [[विभाजन शोधन]],{{sfnp|Habib|Paul|2005}} [[लेक्सबीएफएस]] ,{{sfnp|Bretscher|Corneil|Habib|Paul|2008}} या [[विभाजित अपघटन]]।{{sfnp|Gioan|Paul|2012}} एक बार कोट्री प्रतिनिधित्व का निर्माण हो जाने के बाद, कई परिचित ग्राफ़ समस्याओं को कॉट्रीज़ पर सरल बॉटम-अप गणनाओं के माध्यम से हल किया जा सकता है।
कोग्राफ को रैखिक समय में पहचाना जा सकता है, और वैकल्पिक [[मॉड्यूलर अपघटन|अपघटन]] का उपयोग करके कोग्राफ प्रतिनिधित्व का निर्माण किया जा सकता है,{{sfnp|Corneil|Perl|Stewart|1985}} [[विभाजन शोधन]],{{sfnp|Habib|Paul|2005}} [[लेक्सबीएफएस]] ,{{sfnp|Bretscher|Corneil|Habib|Paul|2008}} या [[विभाजित अपघटन|विभाजित अपघटन इत्यादि है]]।{{sfnp|Gioan|Paul|2012}} एक बार कोट्री प्रतिनिधित्व का निर्माण हो जाने के बाद, कई साधारण ग्राफ़ समस्याओं को कॉट्री पर सरल बॉटम-अप (निचे से ऊपर) गणनाओं के माध्यम से सिद्ध किया जा सकता है।


उदाहरण के लिए, एक कोग्राफ में [[क्लिक समस्या]] को खोजने के लिए, नीचे-ऊपर के क्रम में प्रत्येक सबग्राफ में अधिकतम क्लिक कोट्री के सबट्री द्वारा दर्शाया गया है। 0 लेबल वाले नोड के लिए, उस नोड के बच्चों के लिए गणना की गई क्लिक्स में अधिकतम क्लिक अधिकतम है। 1 लेबल वाले नोड के लिए, अधिकतम क्लिक उस नोड के बच्चों के लिए गणना की गई क्लिक्स का संघ है, और इसका आकार बच्चों के क्लिक आकार के योग के बराबर है। इस प्रकार, कोट्री के प्रत्येक नोड पर संग्रहीत मूल्यों को वैकल्पिक रूप से अधिकतम और योग करके, हम अधिकतम क्लिक आकार की गणना कर सकते हैं, और वैकल्पिक रूप से अधिकतम और यूनियनों को लेकर, हम अधिकतम क्लिक का निर्माण कर सकते हैं। समान बॉटम-अप ट्री कम्प्यूटेशंस मैक्सिमल इंडिपेंडेंट सेट, [[ ग्राफ रंगना ]], मैक्सिमम क्लिक कवर, और हैमिल्टनिसिटी (जो कि [[हैमिल्टनियन पथ समस्या]] का अस्तित्व है) को कोग्राफ के कॉट्री प्रतिनिधित्व से रैखिक समय में गणना करने की अनुमति देता है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}} क्योंकि कोग्राफ ने क्लिक-चौड़ाई को सीमित कर दिया है, कौरसेल के प्रमेय का उपयोग ग्राफ़ के मोनाडिक सेकंड-ऑर्डर लॉजिक (MSO) में किसी भी संपत्ति का परीक्षण करने के लिए किया जा सकता है।<sub>1</sub>) रैखिक समय में कोग्राफ पर।{{sfnp|Courcelle|Makowsky|Rotics|2000}}
उदाहरण के लिए, कोग्राफ में अधिकतम [[क्लिक समस्या|क्लिक]] को ढूंढने के लिए, नीचे-ऊपर के क्रम में प्रत्येक सबग्राफ में अधिकतम क्लिक कोट्री के उपशीर्षक द्वारा दर्शाया गया है। 0 लेबल वाले बिंदु के लिए, उस बिंदु के भाग के लिए गणना की गई क्लिक्स में अधिकतम क्लिक अधिकतम है। 1 लेबल वाले बिंदु के लिए,अधिकतम क्लिक उस बिंदु के भाग के लिए गणना की गई क्लिक्स का समूह है,और इसका आकार अंश के क्लिक आकार के योग के बराबर है। इस प्रकार, कोट्री के प्रत्येक बिंदु पर संग्रहीत मूल्यों को वैकल्पिक प्रकार से अधिकतम और योग करके, हम अधिकतम क्लिक आकार की गणना कर सकते हैं, और वैकल्पिक प्रकार से अधिकतम और   समूहों को लेकर, हम अधिकतम क्लिक का निर्माण कर सकते हैं। समान निचे-ऊपर ट्री गड़ना अधिकतम स्वतंत्र समूह, ग्राफ रंगना, शीर्ष रंग संख्या, अधिकतम क्लिक कवर और हैमिल्टोनसीटी (वह हैमिल्नियन चक्र का अस्तित्व है) को कोग्राफ के कोट्री प्रतिनिधित्व से रैखिक समय में गड़ना करने की अनुमति देता है।{{sfnp|Corneil|Lerchs|Stewart Burlingham|1981}} क्योंकि कोग्राफ ने क्लिक-चौड़ाई को निश्चित सीमा कर दिया है, कौरसेल के प्रमेय का उपयोग ग्राफ़ के मोनाडिक द्वितीय-क्रम तार्किक (MSO<sub>1</sub>) में किसी भी रैखिक समय में कोग्राफ पर गुण का परीक्षण करने के लिए किया जा सकता है।)।{{sfnp|Courcelle|Makowsky|Rotics|2000}}


यह परीक्षण करने की समस्या है कि क्या दिया गया ग्राफ k वर्टिकल दूर है और/या टी किनारों को एक कोग्राफ से दूर है, [[पैरामीटरयुक्त जटिलता]] | निश्चित-पैरामीटर ट्रैक्टेबल है।{{sfnp|Cai|1996}} यह तय करना कि क्या ग्राफ को कोग्राफ में k-एज-डिलीट किया जा सकता है, O में हल किया जा सकता है<sup>*</sup>(2.415<sup>कश्मीर</sup>) समय,{{sfnp|Nastos|Gao|2010}} और k-एज-संपादित O में एक cograph के लिए<sup>*</sup>(4.612<sup>के </सुप>).{{sfnp|Liu|Wang|Guo|Chen|2012}} यदि किसी ग्राफ का सबसे बड़ा प्रेरित कोग्राफ सबग्राफ ग्राफ से k कोने को हटाकर पाया जा सकता है, तो इसे O में पाया जा सकता है<sup>*</sup>(3.30<sup>कश्मीर</sup>) समय।{{sfnp|Nastos|Gao|2010}}
यह परीक्षण करने की समस्या है कि क्या दिया गया ग्राफ के शीर्ष दूर है और/या टी किनारों को कोग्राफ से दूर है, निश्चित-पैरामीटर सरल है।{{sfnp|Cai|1996}} यह तय करना कि क्या ग्राफ को कोग्राफ में के-किनारा-निकलना किया जा सकता है, O<sup>*</sup>(2.415<sup>k</sup>) में सिद्ध किया जा सकता है,{{sfnp|Nastos|Gao|2010}} और के-किनारा-संपादित O<sup>*</sup>(4.612<sup>k</sup>) कोग्राफ में के-किनारा-संपादित किया जा सकता है। <sup>{{sfnp|Liu|Wang|Guo|Chen|2012}}यदि किसी ग्राफ का सबसे बड़ा प्रेरित कोग्राफ सबग्राफ ग्राफ से के कोने को हटाकर पाया जा सकता है, तो इसे (3.30<sup>k)  समय में पाया जा सकता है।<sup>{{sfnp|Nastos|Gao|2010}}


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


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


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


== गणना ==
== गणना ==
n = 1, 2, 3, ... के लिए, n शीर्षों के साथ जुड़े कोग्राफ की संख्या है:
n = 1, 2, 3, ... के लिए, n शीर्षों के साथ जुड़े कोग्राफ की संख्या है:
:1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... {{OEIS|A000669}}
:1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ...(ओइआईसी में अनुक्रम A000669)
एन> 1 के लिए डिस्कनेक्ट किए गए कोग्राफ की समान संख्या होती है, क्योंकि प्रत्येक कॉग्राफ के लिए इसका एक या इसका पूरक ग्राफ जुड़ा होता है।
n > 1 के लिए अलग किए गए कोग्राफ की समान संख्या होती है, क्योंकि प्रत्येक कोग्राफ के लिए इसका पूरक ग्राफ जुड़ा होता है।


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


=== उपवर्ग ===
=== उपवर्ग ===
हर पूरा ग्राफ {{math|''K''<sub>''n''</sub>}} एक कोट्री है, जिसमें एक कॉट्री है जिसमें एक एकल 1-नोड और है {{mvar|n}} पत्तियाँ। इसी तरह, प्रत्येक पूर्ण द्विदलीय ग्राफ {{mvar|''K''<sub>''a'',''b''</sub>}} एक कोग्राफ है। इसका कॉट्री 1-नोड पर निहित है जिसमें दो 0-नोड बच्चे हैं, एक के साथ {{mvar|a}} पत्ते वाले बच्चे और एक साथ {{mvar|b}} पत्ते बच्चे।
सभी पूर्ण ग्राफ {{math|''K''<sub>''n''</sub>}} कोट्री है, जिसमें कोट्री है जिसमें एकल 1-बिंदु एन पत्तियाँ है। इसी प्रकार, प्रत्येक पूर्ण द्विपक्षीय ग्राफ {{mvar|''K''<sub>''a'',''b''</sub>}} कोग्राफ है। इसका कोट्री 1-बिंदु पर निहित है जिसमें दो 0-बिंदु अंश हैं, एक के साथ a पत्ते वाले अंश और एक साथ b पत्ते वाला अंश है। समान आकार के स्वतंत्र समूह के सम्मिलित होने से तुरान ग्राफ बन सकता है; इस प्रकार, यह कोट्री भी है, जिसमें 1-बिंदु पर निहित कोट्री है जिसमें प्रत्येक स्वतंत्र समूह के लिए अंश 0-बिंदु है।
समान आकार के स्वतंत्र सेटों के एक परिवार के शामिल होने से तुरान ग्राफ बन सकता है; इस प्रकार, यह एक कोट्री भी है, जिसमें 1-नोड पर निहित एक कोट्री है जिसमें प्रत्येक स्वतंत्र सेट के लिए एक बच्चा 0-नोड है।


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


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


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


प्रत्येक कॉग्राफ एक दूरी-वंशानुगत ग्राफ है, जिसका अर्थ है कि