कोग्राफ - Revision history

Neeraja at 11:38, 29 August 2023

2023-08-29T11:38:28Z

← Older revision		Revision as of 17:08, 29 August 2023
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), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या P<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 के दशक के बाद से कई लेखकों द्वारा कोग्राफ खोजे गए हैं; प्रारंभिक निर्देशों में युंग (1978), लर्रच्स (1971), सिंसे (1974) और सुमनेर (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}} उनके पास सरल संरचनात्मक अपघटन है जिसमें असंयुक्त समूह और पूर्ण [[पूरा ग्राफ\|ग्राफ]] संचालन सम्मिलित हैं जिन्हें अंकित किये गए ट्री द्वारा संक्षिप्त प्रकार से प्रदर्शित किया जा सकता है, और एल्गोरिदमिक रूप से कई समस्याओं को कुशलतापूर्वक सिद्ध करने के लिए उपयोग किया जाता है जैसे कि से अत्यधिक से अत्यधिक सामान्य ग्राफ वर्गों पर कठिन अधिकतम क्लिक ढूंढना है।

Manidh at 04:44, 21 March 2023

2023-03-21T04:44:25Z

@@ Line 222: / Line 222: @@
    | url = http://www.graphclasses.org | title = Information System on Graph Class Inclusions}}
 * {{mathworld | urlname=Cograph | title=Cograph|mode=cs2}}
 [[Category:Created On 28/02/2023]]
-[[Category:Vigyan Ready]]
+[[Category:Lua-based templates]]

Indicwiki: 34 revisions imported from :alpha:कोग्राफ

2023-03-20T12:56:37Z

34 revisions imported from alpha:कोग्राफ

← Older revision	Revision as of 18:26, 20 March 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-03-20T10:52:20Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 16:22, 20 March 2023
Line 228:		Line 228:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 28/02/2023]]		[[Category:Created On 28/02/2023]]
			[[Category:Vigyan Ready]]

alpha>Shivanidubey: /* कम्प्यूटेशनल गुण */

2023-03-20T05:06:54Z

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

← Older revision		Revision as of 10:36, 20 March 2023
Line 48:		Line 48:
	दो कॉग्राफ [[ग्राफ समरूपता]] हैं यदि उनके समूह (सैद्धांतिक प्रकार में एक ही लेबल के साथ दो आसन्न कोने नहीं हैं) समरूपी हैं। इस तुल्यता के कारण, रैखिक समय में यह निर्धारित कर सकता है कि क्या दो कोग्राफ समरूप हैं, उनके कॉट्रीज़ का निर्माण करके और लेबल किए गए ट्री के लिए रैखिक समय समरूपता परीक्षण क्रियान्वित करना है ।{{sfnp\|Corneil\|Lerchs\|Stewart Burlingham\|1981}}		दो कॉग्राफ [[ग्राफ समरूपता]] हैं यदि उनके समूह (सैद्धांतिक प्रकार में एक ही लेबल के साथ दो आसन्न कोने नहीं हैं) समरूपी हैं। इस तुल्यता के कारण, रैखिक समय में यह निर्धारित कर सकता है कि क्या दो कोग्राफ समरूप हैं, उनके कॉट्रीज़ का निर्माण करके और लेबल किए गए ट्री के लिए रैखिक समय समरूपता परीक्षण क्रियान्वित करना है ।{{sfnp\|Corneil\|Lerchs\|Stewart Burlingham\|1981}}

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

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

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

	=== सुपरक्लास ===		=== सुपरक्लास ===

alpha>Shivanidubey at 05:01, 20 March 2023

2023-03-20T05:01:50Z

← Older revision		Revision as of 10:31, 20 March 2023
Line 32:		Line 32:

	== कोट्री ==		== कोट्री ==
	[[File:Cotree and cograph.svg\|thumb\|upright=1.6\|एक कॉट्री और संबंधित कोग्राफ। कॉग्राफ में प्रत्येक किनारे (u, v) में कॉट्री में u और v के कम से कम आम पूर्वज के लिए एक मिलान रंग होता है।]]कोट्री एक ट्री है जिसका आतंरिक बिंदु को 0 और 1 की संख्या के साथ लेबल किया जाता है। जिसमे सभी कोट्री ''T'' एक कॉग्राफ ''G'' होने को परिभाषित करता है जिसमे की पत्तियां ''T'' शीर्ष के रूप में होती हैं, और ''T'' प्रत्येक बिंदु पर स्थापित उपशीर्षक उस बिंदु से निचे उतरने वाले पत्तों के समूहों द्वारा परिभाषित ''G'' में प्रेरित सबग्राफ के समान होता है;		[[File:Cotree and cograph.svg\|thumb\|upright=1.6\|एक कॉट्री और संबंधित कोग्राफ। कॉग्राफ में प्रत्येक किनारे (u, v) में कॉट्री में u और v के कम से कम आम पूर्वज के लिए एक मिलान रंग होता है।]]कोट्री एक ट्री है जिसका आतंरिक बिंदु को 0 और 1 की संख्या के साथ लेबल किया जाता है। जिसमे सभी कोट्री ''T'' एक कॉग्राफ ''G'' होने को परिभाषित करता है जिसमे की पत्तियां ''T'' शीर्ष के रूप में होती हैं, और ''T'' प्रत्येक बिंदु पर स्थापित उपशीर्षक उस बिंदु से निचे उतरने वाले पत्तों के समूहों द्वारा परिभाषित ''G'' में प्रेरित सबग्राफ के समान होता है;
	* एकल पत्ती बिंदु वाला उपशीर्षक एकल शीर्ष के साथ प्रेरित सबग्राफ के समान होता है।		* एकल पत्ती बिंदु वाला उपशीर्षक एकल शीर्ष के साथ प्रेरित सबग्राफ के समान होता है।
	* 0 लेबल वाले बिंदु पर निहित किया गया उपशीर्षक उस बिंदु के अंश द्वारा परिभाषित सबग्राफ के मिलान की प्रक्रिया के समान होता है।		* 0 लेबल वाले बिंदु पर निहित किया गया उपशीर्षक उस बिंदु के अंश द्वारा परिभाषित सबग्राफ के मिलान की प्रक्रिया के समान होता है।
Line 42:		Line 42:
	कोग्राफ को रैखिक समय में पहचाना जा सकता है, और वैकल्पिक [[मॉड्यूलर अपघटन\|अपघटन]] का उपयोग करके कोग्राफ प्रतिनिधित्व का निर्माण किया जा सकता है,{{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}}

	यह परीक्षण करने की समस्या है कि क्या दिया गया ग्राफ के शीर्ष दूर है और/या टी किनारों को कोग्राफ से दूर है, निश्चित-पैरामीटर सरल है।{{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\|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}}

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

alpha>Sugatha at 07:35, 17 March 2023

2023-03-17T07:35:48Z

Show changes

alpha>Sugatha at 10:50, 16 March 2023

2023-03-16T10:50:28Z

Show changes

alpha>Shivanidubey at 01:47, 16 March 2023

2023-03-16T01:47:53Z

← Older revision		Revision as of 07:17, 16 March 2023
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> से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K1 सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।		[[File:Turan 13-4.svg\|thumb\|तुरान ग्राफ टी(13,4), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या P<sub>4</sub> मुक्त ग्राफ़ है, ग्राफ़ (असतत गणित) जो एकल-शीर्ष ग्राफ K<sub>1</sub> से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K<sub>1</sub> सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।

	1970 के दशक के बाद से कई लेखकों द्वारा कोग्राफ खोजे गए हैं; प्रारंभिक निर्देशों में युंग (1978), लर्रच्स (1971), सिंसे (1974) और सुमनेर (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}} उनके पास सरल संरचनात्मक अपघटन है जिसमें असंयुक्त समूह और पूर्ण [[पूरा ग्राफ\|ग्राफ]] संचालन सम्मिलित हैं जिन्हें अंकित किये गए पेड़ द्वारा संक्षिप्त प्रकार से प्रदर्शित किया जा सकता है, और एल्गोरिदमिक रूप से कई समस्याओं को कुशलतापूर्वक सिद्ध करने के लिए उपयोग किया जाता है जैसे कि से अत्यधिक से अत्यधिक सामान्य ग्राफ वर्गों पर कठिन अधिकतम क्लिक ढूंढना है।

alpha>Shivanidubey: /* गणना */

2023-03-16T01:45:57Z

गणना

← Older revision		Revision as of 07:15, 16 March 2023
Line 54:		Line 54:
	== गणना ==		== गणना ==
	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, ...(ओइआईसी में अनुक्रम ए000669)
	एन> 1 के लिए अलग किए गए कोग्राफ की समान संख्या होती है, क्योंकि प्रत्येक कोग्राफ के लिए इसका पूरक ग्राफ जुड़ा होता है।		एन> 1 के लिए अलग किए गए कोग्राफ की समान संख्या होती है, क्योंकि प्रत्येक कोग्राफ के लिए इसका पूरक ग्राफ जुड़ा होता है।

← Older revision		Revision as of 17:08, 29 August 2023
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), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या P<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 के दशक के बाद से कई लेखकों द्वारा कोग्राफ खोजे गए हैं; प्रारंभिक निर्देशों में युंग (1978), लर्रच्स (1971), सिंसे (1974) और सुमनेर (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}} उनके पास सरल संरचनात्मक अपघटन है जिसमें असंयुक्त समूह और पूर्ण [[पूरा ग्राफ\|ग्राफ]] संचालन सम्मिलित हैं जिन्हें अंकित किये गए ट्री द्वारा संक्षिप्त प्रकार से प्रदर्शित किया जा सकता है, और एल्गोरिदमिक रूप से कई समस्याओं को कुशलतापूर्वक सिद्ध करने के लिए उपयोग किया जाता है जैसे कि से अत्यधिक से अत्यधिक सामान्य ग्राफ वर्गों पर कठिन अधिकतम क्लिक ढूंढना है।

← Older revision		Revision as of 10:36, 20 March 2023
Line 48:		Line 48:
	दो कॉग्राफ [[ग्राफ समरूपता]] हैं यदि उनके समूह (सैद्धांतिक प्रकार में एक ही लेबल के साथ दो आसन्न कोने नहीं हैं) समरूपी हैं। इस तुल्यता के कारण, रैखिक समय में यह निर्धारित कर सकता है कि क्या दो कोग्राफ समरूप हैं, उनके कॉट्रीज़ का निर्माण करके और लेबल किए गए ट्री के लिए रैखिक समय समरूपता परीक्षण क्रियान्वित करना है ।{{sfnp\|Corneil\|Lerchs\|Stewart Burlingham\|1981}}		दो कॉग्राफ [[ग्राफ समरूपता]] हैं यदि उनके समूह (सैद्धांतिक प्रकार में एक ही लेबल के साथ दो आसन्न कोने नहीं हैं) समरूपी हैं। इस तुल्यता के कारण, रैखिक समय में यह निर्धारित कर सकता है कि क्या दो कोग्राफ समरूप हैं, उनके कॉट्रीज़ का निर्माण करके और लेबल किए गए ट्री के लिए रैखिक समय समरूपता परीक्षण क्रियान्वित करना है ।{{sfnp\|Corneil\|Lerchs\|Stewart Burlingham\|1981}}

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

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

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

	=== सुपरक्लास ===		=== सुपरक्लास ===

← Older revision		Revision as of 07:17, 16 March 2023
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> से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K1 सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।		[[File:Turan 13-4.svg\|thumb\|तुरान ग्राफ टी(13,4), एक कोग्राफ का एक उदाहरण]][[ग्राफ सिद्धांत]] में, कोग्राफ, कम करने योग्य पूरक ग्राफ, या P<sub>4</sub> मुक्त ग्राफ़ है, ग्राफ़ (असतत गणित) जो एकल-शीर्ष ग्राफ K<sub>1</sub> से पूरक और असंयुक्त समूह द्वारा उत्पन्न किया जा सकता है। अर्थात कोग्राफ का समूह ग्राफ का सबसे छोटा वर्ग है जिसमे K<sub>1</sub> सम्मिलित है और पूरक और असंयुक्त समूह के अंतर्गत बंद है।

	1970 के दशक के बाद से कई लेखकों द्वारा कोग्राफ खोजे गए हैं; प्रारंभिक निर्देशों में युंग (1978), लर्रच्स (1971), सिंसे (1974) और सुमनेर (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}} उनके पास सरल संरचनात्मक अपघटन है जिसमें असंयुक्त समूह और पूर्ण [[पूरा ग्राफ\|ग्राफ]] संचालन सम्मिलित हैं जिन्हें अंकित किये गए पेड़ द्वारा संक्षिप्त प्रकार से प्रदर्शित किया जा सकता है, और एल्गोरिदमिक रूप से कई समस्याओं को कुशलतापूर्वक सिद्ध करने के लिए उपयोग किया जाता है जैसे कि से अत्यधिक से अत्यधिक सामान्य ग्राफ वर्गों पर कठिन अधिकतम क्लिक ढूंढना है।