विभाजित ग्राफ

This article is about ग्राफ़ जिन्हें समूह और स्वतंत्र समूह में विभाजित किया जा सकता है. For कटौती जो पूर्ण द्विदलीय रेखांकन बनाती है, see विभाजन (ग्राफ सिद्धांत).

विभाजित ग्राफ, समूह और स्वतंत्र सेट में विभाजित।

ग्राफ़ सिद्धांत में, गणित की शाखा विभाजित ग्राफ़ (असतत गणित) है। जिसमें कोने (ग्राफ़ सिद्धांत) क्लिक (ग्राफ़ सिद्धांत) और स्वतंत्र सेट (ग्राफ़ सिद्धांत) में ग्राफ़ विभाजन किया जा सकता है। विभक्त ग्राफ़ का सर्वप्रथम अध्ययन Földes and Hammer (1977a, 1977b) द्वारा किया गया था और स्वतंत्र रूप से Tyshkevich and Chernyak (1979) द्वारा प्रस्तुत किया था।

विभाजित ग्राफ में अधिक विभाजन क्लिक और स्वतंत्र सेट में हो सकते हैं। उदाहरण के लिए, पथ ग्राफ a–b–c विभक्त ग्राफ़ है। जिसके कोने को तीन भिन्न-भिन्न विधि से विभाजित किया जा सकता है।

1. गिरोह {a, b} और स्वतंत्र सेट {c}
2. गिरोह {b, c} और स्वतंत्र सेट {a}
3. गिरोह {b} और स्वतंत्र सेट {a, c}

विभक्त ग्राफ़ को उनके निषिद्ध प्रेरित उप-अनुच्छेदों के संदर्भ में वर्णित किया जा सकता है। यदि ग्राफ विभाजित होता है और यदि कोई प्रेरित सबग्राफ चार या पांच शिखर पर चक्र ग्राफ नहीं होता है और भिन्न-भिन्न किनारों की जोड़ी (4-चक्र का पूरक) होती है।

अन्य ग्राफ समूहों से संबंध

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

चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं, इसलिए यह विभाजित ग्राफ़ भी होते हैं। डबल विभक्त ग्राफ़ प्रत्येक कोने को दोगुना करके विभक्त ग्राफ़ से प्राप्त ग्राफ़ का समूह (इसलिए क्लिक एंटीमैचिंग को प्रेरित करने के लिए और स्वतंत्र सेट मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से सही ग्राफ के पाँच बुनियादी वर्गों के रूप में आता है। जिसमें से {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}मजबूत परफेक्ट ग्राफ प्रमेय} के द्वारा सबूत में अन्य सभी का गठन किया जा सकता है।

यदि विभाजित ग्राफ़ और अंतराल ग्राफ दोनों है, तब इसका पूरक विभाजित ग्राफ़ और तुलनात्मक ग्राफ दोनों है और इसके विपरीत विभाजित तुलनीयता ग्राफ और जिससे कि विभाजन अंतराल ग्राफ भी तीन वर्जित प्रेरित सबग्राफ के समूह के संदर्भ में वर्णित किए जा सकते हैं। विभाजित कोग्राफ बिल्कुल दहलीज ग्राफ हैं। चूँकि विभाजित क्रमचय ग्राफ वास्तव में अंतराल ग्राफ होते हैं जिनमें अंतराल ग्राफ पूरक होते हैं।

ये तिरछे मर्ज किए गए क्रमपरिवर्तन के क्रमपरिवर्तन ग्राफ़ हैं। विभक्त ग्राफ़ में कोक्रोमैटिक नंबर 2 होती है।

एल्गोरिथम समस्याएं

G को विभाजित ग्राफ़ होने देने के लिए क्लिक C और स्वतंत्र सेट i में विभाजित किया गया है। अतः फिर विभाजित ग्राफ में प्रत्येक अधिकतम क्लिक या तो स्वयं C है या i शीर्ष के पड़ोस (ग्राफ सिद्धांत) है। इस प्रकार, अधिकतम क्लिक की पहचान करना आसान है और विभाजित ग्राफ में पूरक रूप से अधिकतम स्वतंत्र सेट किसी भी विभाजित ग्राफ में निम्नलिखित तीन संभावनाओं में से सत्य होना चाहिए।

1. i में शीर्ष x शीर्ष उपस्तिथ है। जैसे कि C ∪ {x} पूर्ण है। इस स्थिति में, C ∪ {x} अधिकतम क्लिक है और i अधिकतम स्वतंत्र समुच्चय है।
2. C में शीर्ष x का अस्तित्व है। जैसे कि i ∪ {x} स्वतंत्र है। इस स्थिति में, i ∪ {x} अधिकतम स्वतंत्र सेट है और C अधिकतम समूह है।
3. C अधिकतम समूह है और i अधिकतम स्वतंत्र समुच्चय है। इस स्थिति में, G का विशिष्ट विभाजन (C, i) समूह और स्वतंत्र सेट में है, C अधिकतम क्लिक है, और i अधिकतम स्वतंत्र सेट है।

कुछ अन्य अनुकूलन समस्याएं जो अधिक सामान्य ग्राफ़ समूहों पर एनपी-पूर्ण हैं। ग्राफ रंग सहित, विभाजित ग्राफ़ पर समान रूप से सीधी हैं। हैमिल्टनियन चक्र खोजना एनपी-पूर्ण रहता है। यहां तक ​​​​कि विभाजित ग्राफ के लिए भी जो दृढ़ता से कॉर्डल ग्राफ होते हैं। यह भी सर्वविदित है कि विभाजित ग्राफ के लिए मिनिमम डोमिनेटिंग सेट समस्या एनपी-पूर्ण रहती है।

डिग्री अनुक्रम

विभक्त ग्राफ़ की उल्लेखनीय संपत्ति यह है कि उन्हें केवल उनके डिग्री अनुक्रम से ही पहचाना जा सकता है। ग्राफ G के डिग्री अनुक्रम को d₁ ≥ d₂ ≥ … ≥ d_n होने देता है और m को i का सबसे बड़ा मान होता है, जैसे कि d_i ≥ i – 1. तब G विभाजित ग्राफ है। यदि,

$\sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.$

यदि ऐसी स्थिति है, तब सबसे बड़ी डिग्री वाले m शीर्ष अधिकतम कोने G में बनाते हैं और शेष शीर्ष स्वतंत्र समुच्चय का निर्माण करते हैं।

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

विभक्त ग्राफ़ की गिनती

रॉयल (2000) ने दिखाया कि n के साथ n-कोने विभाजित ग्राफ कुछ स्पर्नर समूहों के साथ एक-से-पत्राचार में हैं। इस तथ्य का उपयोग करते हुए उन्होंने n शीर्षों पर गैर-समरूपी विभाजन ग्राफ़ की संख्या के लिए सूत्र निर्धारित किया है। और n के छोटे मानों के लिए, n = 1 से प्रारंभ करके ये संख्याएँ हैं।

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (sequence A048194 in the OEIS).

यह ग्राफ गणना परिणाम पहले भी Tyshkevich & Chernyak (1990) द्वारा सिद्ध किया गया था।

संदर्भ

• 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.
• Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", Information Processing Letters, 19: 37–40, doi:10.1016/0020-0190(84)90126-1.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Split graphs having Dilworth number two", Canadian Journal of Mathematics, 29 (3): 666–672, doi:10.4153/CJM-1977-069-1, MR 0463041.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306.
• Hammer, Peter Ladislaw; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica, 1 (3): 275–284, doi:10.1007/BF02579333, MR 0637832.
• Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", Journal of Combinatorial Theory, Series A, 73 (2): 353–359, doi:10.1016/S0097-3165(96)80012-4, MR 1370138.
• McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K_1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494, MR 0730144.
• Merris, Russell (2003), "Split graphs", European Journal of Combinatorics, 24 (4): 413–430, doi:10.1016/S0195-6698(03)00030-1, MR 1975945.
• Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
• Royle, Gordon F. (2000), "Counting set covers and split graphs" (PDF), Journal of Integer Sequences, 3 (2): 00.2.6, MR 1778996.
• Tyshkevich, Regina I. (1980), "[The canonical decomposition of a graph]", Doklady Akademii Nauk SSSR (in Russian), 24: 677–679, MR 0587712{{citation}}: CS1 maint: unrecognized language (link)
• Tyshkevich, Regina I.; Chernyak, A. A. (1979), "Canonical partition of a graph defined by the degrees of its vertices", Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (in Russian), 5: 14–26, MR 0554162{{citation}}: CS1 maint: unrecognized language (link).
• Tyshkevich, Regina I.; Chernyak, A. A. (1990), Еще один метод перечисления непомеченных комбинаторных объектов, Mat. Zametki (in Russian), 48 (6): 98–105, MR 1102626{{citation}}: CS1 maint: unrecognized language (link). Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, doi:10.1007/BF01240267.
• Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), "On graphs and degree sequences: the canonical decomposition", Kibernetika (in Russian), 6: 5–8, MR 0689420{{citation}}: CS1 maint: unrecognized language (link).
• Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322, MR 0803929.

अग्रिम पठन

• A chapter on split graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs".