कोग्राफ: Difference between revisions

Revision as of 19:28, 15 March 2023

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

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

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

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

परिभाषा

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

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

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

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

कोट्री

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

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

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

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

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

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

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

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

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

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

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

गणना

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

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

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

संदर्भ

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.

बाहरी संबंध

[FOOTNOTEJung1978-1] 1.0 ^1.1 Jung (1978).

[FOOTNOTESumner1974-2] Sumner (1974).

[FOOTNOTEBurletUhry1984-3] Burlet & Uhry (1984).

[FOOTNOTECorneilLerchsStewart_Burlingham1981-4] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 Corneil, Lerchs & Stewart Burlingham (1981).

[FOOTNOTECourcelleOlariu2000-5] Courcelle & Olariu (2000).

[FOOTNOTEBoseBussLubiw1998-6] Bose, Buss & Lubiw (1998).

[FOOTNOTEParraScheffler1997-7] Parra & Scheffler (1997).

[FOOTNOTEChristenSelkow1979-8] Christen & Selkow (1979).

[FOOTNOTECorneilPerlStewart1985-9] Corneil, Perl & Stewart (1985).

[FOOTNOTEHabibPaul2005-10] Habib & Paul (2005).

[FOOTNOTEBretscherCorneilHabibPaul2008-11] Bretscher et al. (2008).

[FOOTNOTEGioanPaul2012-12] Gioan & Paul (2012).

[FOOTNOTECourcelleMakowskyRotics2000-13] Courcelle, Makowsky & Rotics (2000).

[FOOTNOTECai1996-14] Cai (1996).

[FOOTNOTENastosGao2010-15] 15.0 ^15.1 Nastos & Gao (2010).

[FOOTNOTELiuWangGuoChen2012-16] Liu et al. (2012).

[FOOTNOTEDamaschke1990-17] Damaschke (1990).

[FOOTNOTEDamaschke1991-18] Damaschke (1991).

[FOOTNOTEGolumbicGurvich2011-19] Golumbic & Gurvich (2011).

[FOOTNOTEBrandstädtLeSpinrad1999-20] 20.0 ^20.1 Brandstädt, Le & Spinrad (1999).

[FOOTNOTEBergeDuchet1984-21] Berge & Duchet (1984).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

@@ Line 16: / Line 16: @@
 === अन्य विशेषताएं ===
-कॉग्राफ के कई वैकल्पिक लक्षण वर्णन दिए जा सकते हैं। उनमें से:
+कोग्राफ के कई वैकल्पिक लक्षण का वर्णन किया जा सकता है। उनमें से:
-* एक कोग्राफ एक ग्राफ है जिसमें [[पथ (ग्राफ सिद्धांत)]] पी शामिल नहीं है<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}}
 * एक कोग्राफ एक ग्राफ है जिसके सभी प्रेरित सबग्राफ में यह गुण होता है कि कोई भी अधिकतम [[क्लिक (ग्राफ सिद्धांत)]] किसी एकल शीर्ष में किसी भी [[अधिकतम स्वतंत्र सेट]] को काटता है।
 * एक कोग्राफ एक ग्राफ है जिसमें प्रत्येक गैर-तुच्छ प्रेरित सबग्राफ में समान पड़ोस के साथ कम से कम दो शिखर होते हैं।

Anonymous

Search

कोग्राफ: Difference between revisions

Namespaces

More

Page actions

Revision as of 19:28, 15 March 2023

Contents

परिभाषा

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

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

कोट्री

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

गणना

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

उपवर्ग

सुपरक्लास

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कोग्राफ: Difference between revisions

Revision as of 19:28, 15 March 2023

परिभाषा

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

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

कोट्री

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

गणना

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

उपवर्ग

सुपरक्लास

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories