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

From Vigyanwiki
No edit summary
No edit summary
Line 11: Line 11:
परिभाषा से, विभाजित ग्राफ़ पूरक (ग्राफ़ सिद्धांत) के अनुसार स्पष्ट रूप से बंद हैं।<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>


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


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

Revision as of 12:16, 17 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".