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

This article is about graphs that can be partitioned into a clique and an independent set. For cuts that form complete bipartite graphs, see split (graph theory).

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

ग्राफ़ सिद्धांत में, गणित की एक शाखा, एक विभाजित ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें वर्टेक्स (ग्राफ़ सिद्धांत) एक क्लिक (ग्राफ़ सिद्धांत) और एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) में ग्राफ़ विभाजन हो सकता है। विभक्त रेखांकन का सर्वप्रथम अध्ययन किसके द्वारा किया गया था? 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}मजबूत परफेक्ट ग्राफ प्रमेय का }।

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

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

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

1. एक शीर्ष उपस्तिथ है x में i ऐसा है कि C ∪ {x} तैयार है। इस स्थिति में, C ∪ {x} एक अधिकतम क्लिक है और i अधिकतम स्वतंत्र समुच्चय है।
2. एक शीर्ष उपस्तिथ है x में C ऐसा है कि 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 सबसे बड़ी डिग्री वाले शीर्ष, और शेष शीर्षों के युग्मों के बीच के सभी किनारों को हटाना; विभाजन इस क्रम में संचालन की संख्या की गणना करता है।

स्प्लिट ग्राफ़ की गिनती

Royle (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".