कॉर्डल ग्राफ

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

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

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

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

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

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

कॉर्डल ग्राफ के सभी पूर्ण उन्मूलन आदेशों के समुच्चय को एंटीमैट्रोइड के मूल शब्दों के रूप में तैयार किया जा सकता है; 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), ट्री (ग्राफ़ सिद्धांत) और उनके सबट्री सम्मिलित हैं।

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

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

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

उपवर्ग

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

विभाजित ग्राफ ऐसे ग्राफ़ होते हैं जो कॉर्डल और कॉर्डल ग्राफ़ के पूरक (ग्राफ़ सिद्धांत) दोनों होते हैं। 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.