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

From Vigyanwiki
(Created page with "{{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 compl...")
 
No edit summary
 
(14 intermediate revisions by 4 users not shown)
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=फोल्ड्स|author2-link=Peter Ladislaw Hammer|last2=हैमर|year=1977a|year2=1977b|txt}} द्वारा किया गया था और स्वतंत्र रूप से {{harvs|author1-link=रेजिना टाइशकेविच|last1=टिशकेविच|last2=चेर्न्याक|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>


चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं। अतः यह विभाजित ग्राफ़ भी होते हैं। '''डबल विभक्त ग्राफ़''' प्रत्येक कोने को दोगुना करके विभक्त ग्राफ़ से प्राप्त ग्राफ़ का समूह (अतः क्लिक मिलान को प्रेरित करने के लिए और स्वतंत्र समूह मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से [[सही ग्राफ]] के पाँच बुनियादी वर्गों के रूप में आता है। जिसमें से (हार्वेटीएक्सटी,चुडनोव्स्की,रॉबर्टसन,सेमुर,थॉमस,2006) [[मजबूत परफेक्ट ग्राफ प्रमेय|मजबूत उत्तम ग्राफ प्रमेय]] के द्वारा प्रमाण में अन्य सभी का गठन किया जा सकता है।


== अन्य ग्राफ परिवारों से संबंध ==
यदि विभाजित ग्राफ़ और [[अंतराल ग्राफ]] दोनों होते है। तब इसका पूरक विभाजित ग्राफ़ और [[तुलनात्मक ग्राफ]] दोनों है और इसके विपरीत विभाजित तुलनीयता ग्राफ और जिससे कि विभाजन अंतराल ग्राफ भी तीन वर्जित प्रेरित सबग्राफ के समूह के संदर्भ में वर्णित किए जा सकते हैं।<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|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}[[मजबूत परफेक्ट ग्राफ प्रमेय]] का }।


यदि एक ग्राफ़ विभाजित ग्राफ़ और एक [[अंतराल ग्राफ]]़ दोनों है, तो इसका पूरक एक विभाजित ग्राफ़ और [[तुलनात्मक ग्राफ]]़ दोनों है, और इसके विपरीत। विभाजित तुलनीयता ग्राफ, और इसलिए विभाजन अंतराल ग्राफ भी, तीन वर्जित प्रेरित सबग्राफ के एक सेट के रूप में चित्रित किए जा सकते हैं।<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 ]] होती है 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|i}} में शीर्ष {{mvar|x}} शीर्ष उपस्तिथ है। जैसे कि {{math|''C'' ∪ {''x''} }}पूर्ण है। इस स्थिति में, {{math|''C'' ∪ {''x''} }}अधिकतम क्लिक है और {{mvar|i}} अधिकतम स्वतंत्र समुच्चय है।
# एक शीर्ष मौजूद है {{mvar|x}} में {{mvar|C}} ऐसा है कि {{math|''i'' ∪ {''x''} }} स्वतंत्र है। इस मामले में, {{math|''i'' ∪ {''x''} }} एक अधिकतम स्वतंत्र सेट है और {{mvar|C}} अधिकतम क्लिक है।
# {{mvar|C}} में शीर्ष {{mvar|x}} का अस्तित्व है। जैसे कि {{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>
== [[डिग्री अनुक्रम]] ==
== [[डिग्री अनुक्रम]] ==
स्प्लिट ग्राफ़ की एक उल्लेखनीय संपत्ति यह है कि उन्हें केवल उनके डिग्री अनुक्रम से ही पहचाना जा सकता है। एक ग्राफ के डिग्री अनुक्रम दें {{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}}


== स्प्लिट ग्राफ़ की गिनती ==
अनैतिक ग्राफ का [[विखंडन]] उस सीमा को मापता है जिस तक यह असमानता सही नहीं हो पाती है। यदि कोई ग्राफ़ विभाजित ग्राफ़ नहीं है, तब किनारों के सम्मिलन और निष्कासन का सबसे छोटा क्रम जो इसे विभाजित ग्राफ़ में बनाता है। सबसे बड़ी डिग्री के साथ m कोने के मध्य सभी विलुप्त किनारों को जोड़कर और जोड़े के मध्य के सभी किनारों को हटाकर प्राप्त किया जा सकता है। शेष शिखर, विभाजन इस क्रम में संचालन की संख्या की गणना करता है।{{sfnp|Hammer|Simeone|1981}}
{{harvtxt|Royle|2000}} ने दिखाया कि n के साथ n-वर्टेक्स स्प्लिट ग्राफ कुछ [[स्पर्नर परिवार]]ों के साथ एक-से-एक पत्राचार में हैं। इस तथ्य का उपयोग करते हुए, उन्होंने n शीर्षों पर गैर-समरूपी विभाजन रेखांकन की संख्या के लिए एक सूत्र निर्धारित किया। n के छोटे मानों के लिए, n = 1 से प्रारंभ करके, ये संख्याएँ हैं
 
== विभक्त ग्राफ़ की गिनती ==
{{harvtxt|रॉयल|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|टाइशकेविच|चेर्न्याक|1990}} द्वारा सिद्ध किया गया था।


==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist|30em}}
{{reflist|30em}}
==संदर्भ==
==संदर्भ==
{{refbegin|30em}}
{{refbegin|30em}}
Line 239: Line 236:
  | mr = 0803929}}.
  | mr = 0803929}}.
{{refend}}
{{refend}}
==अग्रिम पठन==
==अग्रिम पठन==
*A chapter on split graphs appears in the book by [[Martin Charles Golumbic]], "Algorithmic Graph Theory and Perfect Graphs".
*A chapter on split graphs appears in the book by [[Martin Charles Golumbic]], "Algorithmic Graph Theory and Perfect Graphs".
[[Category: ग्राफ परिवार]] [[Category: रेखांकन के चौराहे वर्ग]] [[Category: बिल्कुल सही रेखांकन]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 maint]]
[[Category:CS1 uses русский-language script (ru)]]
[[Category:Created On 28/02/2023]]
[[Category:Created On 28/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ परिवार]]
[[Category:बिल्कुल सही रेखांकन]]
[[Category:रेखांकन के चौराहे वर्ग]]

Latest revision as of 13:14, 22 March 2023

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

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

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

  1. क्लिक {a, b} और स्वतंत्र समूह {c}
  2. क्लिक {b, c} और स्वतंत्र समूह {a}
  3. क्लिक {b} और स्वतंत्र समूह {a, c}

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

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

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

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

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

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

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

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

  1. i में शीर्ष x शीर्ष उपस्तिथ है। जैसे कि C ∪ {x} पूर्ण है। इस स्थिति में, C ∪ {x} अधिकतम क्लिक है और i अधिकतम स्वतंत्र समुच्चय है।
  2. C में शीर्ष x का अस्तित्व है। जैसे कि 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]

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

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

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

यह ग्राफ गणना परिणाम पहले भी टाइशकेविच & चेर्न्याक (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".