कॉर्डल ग्राफ

दो तारों वाला एक चक्र (काला) (हरा)। इस भाग के लिए, ग्राफ़ कॉर्डल है। हालाँकि, एक हरे किनारे को हटाने से एक गैर-कॉर्डल ग्राफ़ प्राप्त होगा। दरअसल, तीन काले किनारों वाला दूसरा हरा किनारा बिना किसी तार के चार लंबाई का एक चक्र बनाएगा।

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

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

उत्तम उन्मूलन और कुशल पहचान

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

Rose, Lueker & Tarjan (1976) (यह सभी देखें Habib et al. 2000) दिखाएं कि कॉर्डल ग्राफ़ का एक आदर्श उन्मूलन क्रम लेक्सिकोग्राफ़िक चौड़ाई-पहली खोज नामक एल्गोरिदम का उपयोग करके कुशलतापूर्वक पाया जा सकता है। यह एल्गोरिदम ग्राफ़ के शीर्षों के विभाजन को सेटों के अनुक्रम में बनाए रखता है; प्रारंभ में इस अनुक्रम में सभी शीर्षों के साथ एक एकल सेट होता है। एल्गोरिथम बार-बार एक शीर्ष चुनता है v अनुक्रम के सबसे पुराने सेट से जिसमें पहले से न चुने गए शीर्ष शामिल हैं, और प्रत्येक सेट को विभाजित करता है S अनुक्रम को दो छोटे उपसमूहों में बाँट दिया गया है, पहले में इसके पड़ोसी शामिल हैं v में S और दूसरे में गैर-पड़ोसी शामिल हैं। जब यह विभाजन प्रक्रिया सभी शीर्षों के लिए निष्पादित की जाती है, तो समुच्चयों के अनुक्रम में एक पूर्ण उन्मूलन क्रम के विपरीत, प्रति समुच्चय एक शीर्ष होता है।

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

कॉर्डल ग्राफ के सभी पूर्ण उन्मूलन आदेशों के सेट को एंटीमैट्रोइड के मूल शब्दों के रूप में तैयार किया जा सकता है; Chandran et al. (2003) किसी दिए गए कॉर्डल ग्राफ के सभी पूर्ण उन्मूलन आदेशों को कुशलतापूर्वक सूचीबद्ध करने के लिए एल्गोरिदम के हिस्से के रूप में एंटीमैट्रोइड्स के साथ इस कनेक्शन का उपयोग करें।

अधिकतम क्लिक्स और ग्राफ़ रंग

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

कॉर्डल ग्राफ़ के ग्राफ़ पर क्लिक करें ़ दोहरे कॉर्डल ग्राफ़ हैं।

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

कॉर्डल ग्राफ़ के रंगीन बहुपद की गणना करना आसान है। एक आदर्श उन्मूलन आदेश खोजें v₁, v₂, …, v_n. होने देना N_i के पड़ोसियों की संख्या के बराबर v_i जो बाद में आता है v_i उस क्रम में। उदाहरण के लिए, N_n = 0. वर्णिक बहुपद बराबर होता है $(x-N_{1})(x-N_{2})\cdots (x-N_{n}).$ (अंतिम कारक बस है x, इसलिए x बहुपद को विभाजित करता है, जैसा कि होना चाहिए।) स्पष्ट रूप से, यह गणना कॉर्डलिटी पर निर्भर करती है।

न्यूनतम विभाजक

किसी भी ग्राफ़ में, एक शीर्ष विभाजक शीर्षों का एक सेट होता है जिसे हटाने से शेष ग्राफ़ डिस्कनेक्ट हो जाता है; एक विभाजक न्यूनतम है यदि इसमें कोई उचित उपसमुच्चय नहीं है जो एक विभाजक भी है। के एक प्रमेय के अनुसार Dirac (1961), कॉर्डल ग्राफ़ ऐसे ग्राफ़ होते हैं जिनमें प्रत्येक न्यूनतम विभाजक एक क्लिक होता है; डिराक ने इस लक्षण वर्णन का उपयोग यह साबित करने के लिए किया कि कॉर्डल ग्राफ़ सही ग्राफ़ हैं।

कॉर्डल ग्राफ़ के परिवार को आगमनात्मक रूप से ऐसे ग्राफ़ के रूप में परिभाषित किया जा सकता है जिनके शीर्षों को तीन गैर-रिक्त उपसमूहों में विभाजित किया जा सकता है A, S, और B, ऐसा है कि $A\cup S$ और $S\cup B$ दोनों कॉर्डल प्रेरित सबग्राफ बनाते हैं, S एक गुट है, और इसका कोई किनारा नहीं है A को B. अर्थात्, वे ऐसे ग्राफ़ हैं जिनमें क्लिक विभाजकों द्वारा छोटे उपग्राफों में पुनरावर्ती अपघटन होता है। इस कारण से, कॉर्डल ग्राफ़ को कभी-कभी विघटित ग्राफ़ भी कहा जाता है।

उपवृक्षों का प्रतिच्छेदन ग्राफ

आठ शीर्षों वाला एक कॉर्डल ग्राफ, छह-नोड पेड़ के आठ उपवृक्षों के प्रतिच्छेदन ग्राफ के रूप में दर्शाया गया है।

कॉर्डल ग्राफ़ का एक वैकल्पिक लक्षण वर्णन, के कारण Gavril (1974), पेड़ (ग्राफ़ सिद्धांत) और उनके उपवृक्ष शामिल हैं।

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

उपवृक्षों के प्रतिच्छेदन के रूप में कॉर्डल ग्राफ़ का प्रतिनिधित्व ग्राफ़ का एक वृक्ष अपघटन बनाता है, जिसमें ग्राफ़ में सबसे बड़े क्लिक के आकार से एक कम के बराबर वृक्ष चौड़ाई होती है; किसी भी ग्राफ जी के वृक्ष अपघटन को इस तरह से कॉर्डल ग्राफ के उपग्राफ के रूप में जी के प्रतिनिधित्व के रूप में देखा जा सकता है। ग्राफ़ का ट्री अपघटन जंक्शन ट्री एल्गोरिदम का जंक्शन ट्री भी है।

अन्य ग्राफ वर्गों से संबंध

उपवर्ग

अंतराल ग्राफ़ पथ ग्राफ़ के उपवृक्षों के प्रतिच्छेदन ग्राफ़ हैं, पेड़ों का एक विशेष मामला। इसलिए, वे कॉर्डल ग्राफ़ का एक उपपरिवार हैं।

विभाजित ग्राफ ़ ऐसे ग्राफ़ होते हैं जो कॉर्डल और कॉर्डल ग्राफ़ के पूरक (ग्राफ़ सिद्धांत) दोनों होते हैं। Bender, Richmond & Wormald (1985) ने दिखाया कि, सीमा में n अनन्त तक जाता है, का अंश n-वर्टेक्स कॉर्डल कॉग्रफ़़ जो विभाजित हैं, एक के करीब पहुंचते हैं।

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

सशक्त रूप से कॉर्डल ग्राफ़ ऐसे ग्राफ़ होते हैं जो कॉर्डल होते हैं और उनमें कोई नहीं होता है n-सूर्य (के लिए n ≥ 3) एक प्रेरित उपसमूह के रूप में। यहाँ एक n-सूर्य एक है n-वर्टेक्स कॉर्डल ग्राफ़ G के संग्रह के साथ n डिग्री-दो शीर्ष, हैमिल्टनियन चक्र के किनारों से सटे हुएG.

के-पेड़|K-पेड़ कॉर्डल ग्राफ़ होते हैं जिनमें सभी अधिकतम क्लिक और सभी अधिकतम क्लिक विभाजक का आकार समान होता है। अपोलोनियन नेटवर्क कॉर्डल मैक्सिमम समतलीय ग्राफ, या समकक्ष प्लेनर 3-पेड़ हैं।मैक्सिमम बाह्यतलीय ग्राफ ़ 2-पेड़ों का एक उपवर्ग हैं, और इसलिए कॉर्डल भी हैं।

सुपरक्लासेस

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

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

कॉर्डल पूर्णताएं और ट्रीविड्थ

Main article: Chordal completion

अगर G एक मनमाना ग्राफ़ है, एक कॉर्डल समापन G (या न्यूनतम भरण) एक कॉर्डल ग्राफ है जिसमें शामिल है G एक सबग्राफ के रूप में। न्यूनतम भरण का पैरामीटरयुक्त संस्करण पैरामीटरीकृत जटिलता है, और इसके अलावा, पैरामीटरयुक्त उपघातीय समय में हल करने योग्य है। की वृक्ष चौड़ाई G इस क्लिक आकार को कम करने के लिए चुने गए कॉर्डल पूर्णता के अधिकतम क्लिक में शीर्षों की संख्या से एक कम है। के-वृक्ष|k-पेड़ वे ग्राफ़ होते हैं जिनमें उनकी ट्रीविड्थ को इससे बड़ी संख्या तक बढ़ाए बिना कोई अतिरिक्त किनारा नहीं जोड़ा जा सकता हैk. इसलिए k-पेड़ अपनी स्वयं की कॉर्डल पूर्णताएं हैं, और कॉर्डल ग्राफ़ का एक उपवर्ग बनाते हैं। कॉर्डल पूर्णताओं का उपयोग ग्राफ़ के कई अन्य संबंधित वर्गों को चिह्नित करने के लिए भी किया जा सकता है।

संदर्भ

• Agnarsson, Geir (2003), "On chordal graphs and their chromatic polynomials", Mathematica Scandinavica, 93 (2): 240–246, doi:10.7146/math.scand.a-14421, MR 2009583.
• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
• Berge, Claude (1967), "Some Classes of Perfect Graphs", in Harary, Frank (ed.), Graph Theory and Theoretical Physics, Academic Press, pp. 155–165, MR 0232694.
• Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics, 21 (3): 573–591, doi:10.1137/050637091.
• Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), "Two strikes against perfect phylogeny" (PDF), Proc. of 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Computer Science, vol. 623, pp. 273–283, doi:10.1007/3-540-55719-9_80, hdl:1874/16653.
• Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), "Enumerating and characterizing the perfect elimination orderings of a chordal graph" (PDF), Theoretical Computer Science, 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4.
• Dirac, G. A. (1961), "On rigid circuit graphs" (PDF), Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25 (1–2): 71–76, doi:10.1007/BF02992776, MR 0130190, S2CID 120608513.
• Fomin, Fedor V.; Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput., 42 (6): 2197–2216, arXiv:1104.2230, doi:10.1137/11085390X, S2CID 934546.
• Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific J. Math., 15 (3): 835–855, doi:10.2140/pjm.1965.15.835.
• Gavril, Fănică (1974), "The intersection graphs of subtrees in trees are exactly the chordal graphs", Journal of Combinatorial Theory, Series B, 16: 47–56, doi:10.1016/0095-8956(74)90094-X.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press.
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing", Theoretical Computer Science, 234 (1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7.
• Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput., 28 (5): 1906–1922, doi:10.1137/S0097539796303044.
• Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
• Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics, 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR 1478250.
• Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069.
• Rose, D.; Lueker, George; Tarjan, Robert E. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021, MR 0408312.
• Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
• Szwarcfiter, J.L.; Bornstein, C.F. (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics, 7 (2): 331–336, doi:10.1137/s0895480191223191, hdl:11422/1497.

बाहरी संबंध

• Information System on Graph Class Inclusions: chordal graph
• Weisstein, Eric W. "Chordal Graph". MathWorld.