विभाजित ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Graph which partitions into a clique and independent set}}
{{short description|Graph which partitions into a clique and independent set}}
{{about|graphs that can be partitioned into a clique and an independent set|cuts that form complete bipartite graphs|split (graph theory)}}
{{about|ग्राफ़ जिन्हें समूह और स्वतंत्र समूह में विभाजित किया जा सकता है|कटौती जो पूर्ण द्विदलीय रेखांकन बनाती है|विभाजन (ग्राफ सिद्धांत)}}
[[File:Split graph.svg|thumb|240px|एक विभाजित ग्राफ, एक समूह और एक स्वतंत्र सेट में विभाजित।]]ग्राफ़ सिद्धांत में, गणित की एक शाखा, एक विभाजित ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें वर्टेक्स (ग्राफ़ सिद्धांत) एक क्लिक (ग्राफ़ सिद्धांत) और एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) में ग्राफ़ विभाजन हो सकता है। विभक्त रेखांकन का सर्वप्रथम अध्ययन किसके द्वारा किया गया था? {{harvs|last1=Földes|author2-link=Peter Ladislaw Hammer|last2=Hammer|year=1977a|year2=1977b|txt}}, और स्वतंत्र रूप से प्रस्तुत किया {{harvs|author1-link=Regina Tyshkevich|last1=Tyshkevich|last2=Chernyak|year=1979|txt}}.<ref>{{harvtxt|Földes|Hammer|1977a}} had a more general definition, in which the graphs they called split graphs also included [[bipartite graph]]s (that is, graphs that be partitioned into two independent sets) and the [[complement (graph theory)|complements]] of bipartite graphs (that is, graphs that can be partitioned into two cliques). {{harvtxt|Földes|Hammer|1977b}} use the definition given here, which has been followed in the subsequent literature; for instance, it is {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Definition 3.2.3, p.41.</ref>
[[File:Split graph.svg|thumb|240px|विभाजित ग्राफ, समूह और स्वतंत्र सेट में विभाजित।]]ग्राफ़ सिद्धांत में, गणित की शाखा विभाजित ग्राफ़ (असतत गणित) है। जिसमें वर्टेक्स (ग्राफ़ सिद्धांत) क्लिक (ग्राफ़ सिद्धांत) और स्वतंत्र सेट (ग्राफ़ सिद्धांत) में ग्राफ़ विभाजन हो सकता है। विभक्त रेखांकन का सर्वप्रथम अध्ययन किसके द्वारा किया गया था? {{harvs|last1=Földes|author2-link=Peter Ladislaw Hammer|last2=Hammer|year=1977a|year2=1977b|txt}}, और स्वतंत्र रूप से प्रस्तुत किया {{harvs|author1-link=Regina Tyshkevich|last1=Tyshkevich|last2=Chernyak|year=1979|txt}}.<ref>{{harvtxt|Földes|Hammer|1977a}} had a more general definition, in which the graphs they called split graphs also included [[bipartite graph]]s (that is, graphs that be partitioned into two independent sets) and the [[complement (graph theory)|complements]] of bipartite graphs (that is, graphs that can be partitioned into two cliques). {{harvtxt|Földes|Hammer|1977b}} use the definition given here, which has been followed in the subsequent literature; for instance, it is {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Definition 3.2.3, p.41.</ref>
एक विभाजित ग्राफ में एक से अधिक विभाजन एक क्लिक और एक स्वतंत्र सेट में हो सकते हैं; उदाहरण के लिए, [[पथ ग्राफ]] {{math|''a''–''b''–''c''}} एक स्प्लिट ग्राफ़ है, जिसके कोने को तीन अलग-अलग तरीकों से विभाजित किया जा सकता है:
विभाजित ग्राफ में से अधिक विभाजन क्लिक और स्वतंत्र सेट में हो सकते हैं; उदाहरण के लिए, [[पथ ग्राफ]] {{math|''a''–''b''–''c''}} स्प्लिट ग्राफ़ है, जिसके कोने को तीन अलग-अलग तरीकों से विभाजित किया जा सकता है:
#द क्लिक {{math|{''a'', ''b''} }} और स्वतंत्र सेट {{math|{''c''} }}
#द क्लिक {{math|{''a'', ''b''} }} और स्वतंत्र सेट {{math|{''c''} }}
#द क्लिक {{math|{''b'', ''c''} }} और स्वतंत्र सेट {{math|{''a''} }}
#द क्लिक {{math|{''b'', ''c''} }} और स्वतंत्र सेट {{math|{''a''} }}
#द क्लिक {{math|{''b''} }} और स्वतंत्र सेट {{math|{''a'', ''c''} }}
#द क्लिक {{math|{''b''} }} और स्वतंत्र सेट {{math|{''a'', ''c''} }}


स्प्लिट ग्राफ़ को उनके निषिद्ध प्रेरित उप-अनुच्छेदों के संदर्भ में वर्णित किया जा सकता है: एक ग्राफ विभाजित होता है यदि और केवल यदि कोई [[प्रेरित सबग्राफ]] चार या पांच शिखर पर एक [[चक्र ग्राफ]] नहीं होता है, या अलग-अलग किनारों की एक जोड़ी (4-चक्र का पूरक)।<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151.</ref>
स्प्लिट ग्राफ़ को उनके निषिद्ध प्रेरित उप-अनुच्छेदों के संदर्भ में वर्णित किया जा सकता है: ग्राफ विभाजित होता है यदि और केवल यदि कोई [[प्रेरित सबग्राफ]] चार या पांच शिखर पर [[चक्र ग्राफ]] नहीं होता है, या अलग-अलग किनारों की जोड़ी (4-चक्र का पूरक)।<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151.</ref>




== अन्य ग्राफ परिवारों से संबंध ==
== अन्य ग्राफ परिवारों से संबंध ==
परिभाषा से, पूरक (ग्राफ़ सिद्धांत) के अनुसार विभाजित ग्राफ़ स्पष्ट रूप से बंद हैं।<ref>{{harvtxt|Golumbic|1980}}, Theorem 6.1, p. 150.</ref> स्प्लिट ग्राफ़ के अन्य लक्षण वर्णन में पूरकता सम्मिलित है: वे [[कॉर्डल ग्राफ]]़ हैं, जिनमें से पूरक (ग्राफ़ सिद्धांत) भी कॉर्डल हैं।<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 3.2.3, p. 41.</ref> जिस तरह कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के [[ चौराहा ग्राफ ]]़ हैं, स्प्लिट ग्राफ़ [[स्टार ग्राफ]]़ के अलग-अलग सबस्टार्स के इंटरसेक्शन ग्राफ़ हैं।<ref>{{harvtxt|McMorris|Shier|1983}}; {{harvtxt|Voss|1985}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 4.4.2, p. 52.</ref> [[लगभग सभी]] कॉर्डल ग्राफ़ स्प्लिट ग्राफ़ होते हैं; अर्थात्, उस सीमा में जब n अनंत तक जाता है, n-वर्टेक्स कॉर्डल ग्राफ़ का अंश जो विभाजित होता है वह एक तक पहुंचता है।<ref>{{harvtxt|Bender|Richmond|Wormald|1985}}.</ref>
परिभाषा से, पूरक (ग्राफ़ सिद्धांत) के अनुसार विभाजित ग्राफ़ स्पष्ट रूप से बंद हैं।<ref>{{harvtxt|Golumbic|1980}}, Theorem 6.1, p. 150.</ref> स्प्लिट ग्राफ़ के अन्य लक्षण वर्णन में पूरकता सम्मिलित है: वे [[कॉर्डल ग्राफ]]़ हैं, जिनमें से पूरक (ग्राफ़ सिद्धांत) भी कॉर्डल हैं।<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 3.2.3, p. 41.</ref> जिस तरह कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के [[ चौराहा ग्राफ |चौराहा ग्राफ]] ़ हैं, स्प्लिट ग्राफ़ [[स्टार ग्राफ]]़ के अलग-अलग सबस्टार्स के इंटरसेक्शन ग्राफ़ हैं।<ref>{{harvtxt|McMorris|Shier|1983}}; {{harvtxt|Voss|1985}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 4.4.2, p. 52.</ref> [[लगभग सभी]] कॉर्डल ग्राफ़ स्प्लिट ग्राफ़ होते हैं; अर्थात्, उस सीमा में जब n अनंत तक जाता है, n-वर्टेक्स कॉर्डल ग्राफ़ का अंश जो विभाजित होता है वह तक पहुंचता है।<ref>{{harvtxt|Bender|Richmond|Wormald|1985}}.</ref>
चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं, इसलिए विभाजित ग्राफ़ भी होते हैं। डबल स्प्लिट ग्राफ़, हर वर्टेक्स को दोगुना करके स्प्लिट ग्राफ़ से प्राप्त ग्राफ़ का एक परिवार (इसलिए क्लिक एक एंटीमैचिंग को प्रेरित करने के लिए आता है और स्वतंत्र सेट एक मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से [[सही ग्राफ]]़ के पाँच बुनियादी वर्गों में से एक के रूप में आता है जिसमें से अन्य सभी को सबूत में बनाया जा सकता है {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}[[मजबूत परफेक्ट ग्राफ प्रमेय]] का }।
चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं, इसलिए विभाजित ग्राफ़ भी होते हैं। डबल स्प्लिट ग्राफ़, हर वर्टेक्स को दोगुना करके स्प्लिट ग्राफ़ से प्राप्त ग्राफ़ का परिवार (इसलिए क्लिक एंटीमैचिंग को प्रेरित करने के लिए आता है और स्वतंत्र सेट मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से [[सही ग्राफ]]<nowiki>़ के पाँच बुनियादी वर्गों में से के रूप में आता है जिसमें से अन्य सभी को सबूत में बनाया जा सकता है {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}</nowiki>[[मजबूत परफेक्ट ग्राफ प्रमेय]] का }।


यदि एक ग्राफ़ विभाजित ग्राफ़ और एक [[अंतराल ग्राफ]]़ दोनों है, तो इसका पूरक एक विभाजित ग्राफ़ और [[तुलनात्मक ग्राफ]]़ दोनों है, और इसके विपरीत। विभाजित तुलनीयता ग्राफ, और इसलिए विभाजन अंतराल ग्राफ भी, तीन वर्जित प्रेरित सबग्राफ के एक सेट के रूप में चित्रित किए जा सकते हैं।<ref>{{harvtxt|Földes|Hammer|1977b}}; {{harvtxt|Golumbic|1980}}, Theorem 9.7, page 212.</ref> स्प्लिट [[कोग्राफ]] बिल्कुल [[दहलीज ग्राफ]] हैं। विभाजित क्रमचय ग्राफ वास्तव में अंतराल ग्राफ होते हैं जिनमें अंतराल ग्राफ पूरक होते हैं;<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.</ref>
यदि ग्राफ़ विभाजित ग्राफ़ और [[अंतराल ग्राफ]]़ दोनों है, तो इसका पूरक विभाजित ग्राफ़ और [[तुलनात्मक ग्राफ]]़ दोनों है, और इसके विपरीत। विभाजित तुलनीयता ग्राफ, और इसलिए विभाजन अंतराल ग्राफ भी, तीन वर्जित प्रेरित सबग्राफ के सेट के रूप में चित्रित किए जा सकते हैं।<ref>{{harvtxt|Földes|Hammer|1977b}}; {{harvtxt|Golumbic|1980}}, Theorem 9.7, page 212.</ref> स्प्लिट [[कोग्राफ]] बिल्कुल [[दहलीज ग्राफ]] हैं। विभाजित क्रमचय ग्राफ वास्तव में अंतराल ग्राफ होते हैं जिनमें अंतराल ग्राफ पूरक होते हैं;<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.</ref>
ये तिरछे मर्ज किए गए क्रमपरिवर्तन के क्रमपरिवर्तन ग्राफ़ हैं।{{sfnp|Kézdy|Snevily|Wang|1996}} स्प्लिट ग्राफ़ में [[ cocoloring ]] होती है 2.
ये तिरछे मर्ज किए गए क्रमपरिवर्तन के क्रमपरिवर्तन ग्राफ़ हैं।{{sfnp|Kézdy|Snevily|Wang|1996}} स्प्लिट ग्राफ़ में [[ cocoloring |cocoloring]] होती है 2.


== एल्गोरिथम समस्याएं ==
== एल्गोरिथम समस्याएं ==
होने देना {{mvar|G}} एक विभाजित ग्राफ़ हो, जिसे एक क्लिक में विभाजित किया गया हो {{mvar|C}} और एक स्वतंत्र सेट {{mvar|i}}. फिर विभाजित ग्राफ में प्रत्येक [[अधिकतम क्लिक]] या तो है {{mvar|C}} खुद, या एक शीर्ष के [[पड़ोस (ग्राफ सिद्धांत)]]। {{mvar|i}}. इस प्रकार, अधिकतम क्लिक की पहचान करना आसान है, और एक विभाजित ग्राफ में पूरक रूप से [[अधिकतम स्वतंत्र सेट]]। किसी भी विभाजित ग्राफ में, निम्नलिखित तीन संभावनाओं में से एक सत्य होना चाहिए:<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.2, p. 150.</ref>
होने देना {{mvar|G}} विभाजित ग्राफ़ हो, जिसे क्लिक में विभाजित किया गया हो {{mvar|C}} और स्वतंत्र सेट {{mvar|i}}. फिर विभाजित ग्राफ में प्रत्येक [[अधिकतम क्लिक]] या तो है {{mvar|C}} खुद, या शीर्ष के [[पड़ोस (ग्राफ सिद्धांत)]]। {{mvar|i}}. इस प्रकार, अधिकतम क्लिक की पहचान करना आसान है, और विभाजित ग्राफ में पूरक रूप से [[अधिकतम स्वतंत्र सेट]]। किसी भी विभाजित ग्राफ में, निम्नलिखित तीन संभावनाओं में से सत्य होना चाहिए:<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.2, p. 150.</ref>
# एक शीर्ष उपस्तिथ है {{mvar|x}} में {{mvar|i}} ऐसा है कि {{math|''C'' ∪ {''x''} }} तैयार है। इस स्थिति में, {{math|''C'' ∪ {''x''} }} एक अधिकतम क्लिक है और {{mvar|i}} अधिकतम स्वतंत्र समुच्चय है।
# शीर्ष उपस्तिथ है {{mvar|x}} में {{mvar|i}} ऐसा है कि {{math|''C'' ∪ {''x''} }} तैयार है। इस स्थिति में, {{math|''C'' ∪ {''x''} }} अधिकतम क्लिक है और {{mvar|i}} अधिकतम स्वतंत्र समुच्चय है।
# एक शीर्ष उपस्तिथ है {{mvar|x}} में {{mvar|C}} ऐसा है कि {{math|''i'' ∪ {''x''} }} स्वतंत्र है। इस स्थिति में, {{math|''i'' ∪ {''x''} }} एक अधिकतम स्वतंत्र सेट है और {{mvar|C}} अधिकतम क्लिक है।
# शीर्ष उपस्तिथ है {{mvar|x}} में {{mvar|C}} ऐसा है कि {{math|''i'' ∪ {''x''} }} स्वतंत्र है। इस स्थिति में, {{math|''i'' ∪ {''x''} }} अधिकतम स्वतंत्र सेट है और {{mvar|C}} अधिकतम क्लिक है।
# {{mvar|C}} एक अधिक से अधिक गुट है और {{mvar|i}} एक अधिकतम स्वतंत्र सेट है। इस स्थिति में, {{mvar|G}} का एक अनूठा विभाजन है {{math|(''C'', ''i'')}} एक समूह और एक स्वतंत्र सेट में, {{mvar|C}} अधिकतम क्लिक है, और {{mvar|i}} अधिकतम स्वतंत्र सेट है।
# {{mvar|C}} अधिक से अधिक गुट है और {{mvar|i}} अधिकतम स्वतंत्र सेट है। इस स्थिति में, {{mvar|G}} का अनूठा विभाजन है {{math|(''C'', ''i'')}} समूह और स्वतंत्र सेट में, {{mvar|C}} अधिकतम क्लिक है, और {{mvar|i}} अधिकतम स्वतंत्र सेट है।


कुछ अन्य अनुकूलन समस्याएं जो अधिक सामान्य ग्राफ़ परिवारों पर एनपी-पूर्ण हैं, [[ग्राफ रंग]] सहित, विभाजित ग्राफ़ पर समान रूप से सीधी हैं। [[हैमिल्टनियन चक्र]] ढूँढना एनपी-पूर्ण रहता है, यहां तक ​​​​कि विभाजित ग्राफ के लिए भी जो दृढ़ता से कॉर्डल ग्राफ हैं।<ref>{{harvtxt|Müller|1996}}</ref> यह भी सर्वविदित है कि स्प्लिट ग्राफ के लिए मिनिमम डोमिनेटिंग सेट प्रॉब्लम एनपी-कंप्लीट रहती है।<ref>{{harvtxt|Bertossi|1984}}</ref>
कुछ अन्य अनुकूलन समस्याएं जो अधिक सामान्य ग्राफ़ परिवारों पर एनपी-पूर्ण हैं, [[ग्राफ रंग]] सहित, विभाजित ग्राफ़ पर समान रूप से सीधी हैं। [[हैमिल्टनियन चक्र]] ढूँढना एनपी-पूर्ण रहता है, यहां तक ​​​​कि विभाजित ग्राफ के लिए भी जो दृढ़ता से कॉर्डल ग्राफ हैं।<ref>{{harvtxt|Müller|1996}}</ref> यह भी सर्वविदित है कि स्प्लिट ग्राफ के लिए मिनिमम डोमिनेटिंग सेट प्रॉब्लम एनपी-कंप्लीट रहती है।<ref>{{harvtxt|Bertossi|1984}}</ref>
Line 27: Line 27:


== [[डिग्री अनुक्रम]] ==
== [[डिग्री अनुक्रम]] ==
स्प्लिट ग्राफ़ की एक उल्लेखनीय संपत्ति यह है कि उन्हें केवल उनके डिग्री अनुक्रम से ही पहचाना जा सकता है। एक ग्राफ के डिग्री अनुक्रम दें {{mvar|G}} होना {{math|''d''{{sub|1}} ≥ ''d''{{sub|2}} ≥ … ≥ ''d{{sub|n}}''}}, और जाने {{mvar|m}} का सबसे बड़ा मान हो {{mvar|i}} ऐसा है कि {{math|''d{{sub|i}}'' ≥ ''i'' – 1}}. तब {{mvar|G}} एक विभाजित ग्राफ है यदि और केवल यदि
स्प्लिट ग्राफ़ की उल्लेखनीय संपत्ति यह है कि उन्हें केवल उनके डिग्री अनुक्रम से ही पहचाना जा सकता है। ग्राफ के डिग्री अनुक्रम दें {{mvar|G}} होना {{math|''d''{{sub|1}} ≥ ''d''{{sub|2}} ≥ … ≥ ''d{{sub|n}}''}}, और जाने {{mvar|m}} का सबसे बड़ा मान हो {{mvar|i}} ऐसा है कि {{math|''d{{sub|i}}'' ≥ ''i'' – 1}}. तब {{mvar|G}} विभाजित ग्राफ है यदि और केवल यदि
:<math>\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.</math>
:<math>\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.</math>
यदि ऐसा होता है, तो {{mvar|m}} सबसे बड़ी डिग्री वाले शीर्ष एक अधिकतम क्लिक बनाते हैं {{mvar|G}}, और शेष शीर्ष एक स्वतंत्र समुच्चय का निर्माण करते हैं।<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Tyshkevich|1980}}; {{harvtxt|Tyshkevich|Melnikow|Kotov|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.7 and Corollary 6.8, p. 154; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 13.3.2, p. 203. {{harvtxt|Merris|2003}} further investigates the degree sequences of split graphs.</ref>
यदि ऐसा होता है, तो {{mvar|m}} सबसे बड़ी डिग्री वाले शीर्ष अधिकतम क्लिक बनाते हैं {{mvar|G}}, और शेष शीर्ष स्वतंत्र समुच्चय का निर्माण करते हैं।<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Tyshkevich|1980}}; {{harvtxt|Tyshkevich|Melnikow|Kotov|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.7 and Corollary 6.8, p. 154; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 13.3.2, p. 203. {{harvtxt|Merris|2003}} further investigates the degree sequences of split graphs.</ref>
एक मनमाना ग्राफ का [[विखंडन]] उस सीमा को मापता है जिस तक यह असमानता सही नहीं हो पाती है। यदि कोई ग्राफ़ विभाजित ग्राफ़ नहीं है, तो किनारों के सम्मिलन और निष्कासन का सबसे छोटा क्रम जो इसे विभाजित ग्राफ़ में बनाता है, सभी लापता किनारों को जोड़कर प्राप्त किया जा सकता है {{mvar|m}} सबसे बड़ी डिग्री वाले शीर्ष, और शेष शीर्षों के युग्मों के बीच के सभी किनारों को हटाना; विभाजन इस क्रम में संचालन की संख्या की गणना करता है।{{sfnp|Hammer|Simeone|1981}}
मनमाना ग्राफ का [[विखंडन]] उस सीमा को मापता है जिस तक यह असमानता सही नहीं हो पाती है। यदि कोई ग्राफ़ विभाजित ग्राफ़ नहीं है, तो किनारों के सम्मिलन और निष्कासन का सबसे छोटा क्रम जो इसे विभाजित ग्राफ़ में बनाता है, सभी लापता किनारों को जोड़कर प्राप्त किया जा सकता है {{mvar|m}} सबसे बड़ी डिग्री वाले शीर्ष, और शेष शीर्षों के युग्मों के बीच के सभी किनारों को हटाना; विभाजन इस क्रम में संचालन की संख्या की गणना करता है।{{sfnp|Hammer|Simeone|1981}}


== स्प्लिट ग्राफ़ की गिनती ==
== स्प्लिट ग्राफ़ की गिनती ==
{{harvtxt|Royle|2000}} ने दिखाया कि n के साथ n-वर्टेक्स स्प्लिट ग्राफ कुछ [[स्पर्नर परिवार]]ों के साथ एक-से-एक पत्राचार में हैं। इस तथ्य का उपयोग करते हुए, उन्होंने n शीर्षों पर गैर-समरूपी विभाजन रेखांकन की संख्या के लिए एक सूत्र निर्धारित किया। n के छोटे मानों के लिए, n = 1 से प्रारंभ करके, ये संख्याएँ हैं
{{harvtxt|Royle|2000}} ने दिखाया कि n के साथ n-वर्टेक्स स्प्लिट ग्राफ कुछ [[स्पर्नर परिवार]]ों के साथ एक-से-पत्राचार में हैं। इस तथ्य का उपयोग करते हुए, उन्होंने n शीर्षों पर गैर-समरूपी विभाजन रेखांकन की संख्या के लिए सूत्र निर्धारित किया। n के छोटे मानों के लिए, n = 1 से प्रारंभ करके, ये संख्याएँ हैं
:1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... {{OEIS|id = A048194}}.
:1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... {{OEIS|id = A048194}}.
यह [[ग्राफ गणना]] परिणाम पहले भी सिद्ध करना हुआ था {{harvtxt|Tyshkevich|Chernyak|1990}}.
यह [[ग्राफ गणना]] परिणाम पहले भी सिद्ध करना हुआ था {{harvtxt|Tyshkevich|Chernyak|1990}}.

Revision as of 23:13, 13 March 2023

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

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

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

  1. द क्लिक {a, b} और स्वतंत्र सेट {c}
  2. द क्लिक {b, c} और स्वतंत्र सेट {a}
  3. द क्लिक {b} और स्वतंत्र सेट {a, c}

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


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

परिभाषा से, पूरक (ग्राफ़ सिद्धांत) के अनुसार विभाजित ग्राफ़ स्पष्ट रूप से बंद हैं।[3] स्प्लिट ग्राफ़ के अन्य लक्षण वर्णन में पूरकता सम्मिलित है: वे कॉर्डल ग्राफ़ हैं, जिनमें से पूरक (ग्राफ़ सिद्धांत) भी कॉर्डल हैं।[4] जिस तरह कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के चौराहा ग्राफ ़ हैं, स्प्लिट ग्राफ़ स्टार ग्राफ़ के अलग-अलग सबस्टार्स के इंटरसेक्शन ग्राफ़ हैं।[5] लगभग सभी कॉर्डल ग्राफ़ स्प्लिट ग्राफ़ होते हैं; अर्थात्, उस सीमा में जब n अनंत तक जाता है, n-वर्टेक्स कॉर्डल ग्राफ़ का अंश जो विभाजित होता है वह तक पहुंचता है।[6] चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं, इसलिए विभाजित ग्राफ़ भी होते हैं। डबल स्प्लिट ग्राफ़, हर वर्टेक्स को दोगुना करके स्प्लिट ग्राफ़ से प्राप्त ग्राफ़ का परिवार (इसलिए क्लिक एंटीमैचिंग को प्रेरित करने के लिए आता है और स्वतंत्र सेट मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से सही ग्राफ़ के पाँच बुनियादी वर्गों में से के रूप में आता है जिसमें से अन्य सभी को सबूत में बनाया जा सकता है {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}मजबूत परफेक्ट ग्राफ प्रमेय का }।

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

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

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

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

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


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

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

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

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

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).

टिप्पणियाँ

  1. Földes & Hammer (1977a) had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). Földes & Hammer (1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is Brandstädt, Le & Spinrad (1999), Definition 3.2.3, p.41.
  2. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.
  3. Golumbic (1980), Theorem 6.1, p. 150.
  4. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.
  5. McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.
  6. Bender, Richmond & Wormald (1985).
  7. Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.
  8. Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  9. Kézdy, Snevily & Wang (1996).
  10. Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.
  11. Müller (1996)
  12. Bertossi (1984)
  13. Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.
  14. Hammer & Simeone (1981).


संदर्भ


अग्रिम पठन

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