View source for विभाजित ग्राफ

{{short description|Graph which partitions into a clique and independent set}}
{{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>
विभाजित ग्राफ में अधिक विभाजन क्लिक और स्वतंत्र समूह में हो सकते हैं। उदाहरण के लिए, [[पथ ग्राफ]] {{math|''a''–''b''–''c''}} विभक्त ग्राफ़ है। जिसके कोने को तीन भिन्न-भिन्न विधि से विभाजित किया जा सकता है।
#गिरोह {{math|{''a'', ''b''} }} और स्वतंत्र समूह {{math|{''c''} }}
#गिरोह {{math|{''b'', ''c''} }} और स्वतंत्र समूह {{math|{''a''} }}
#गिरोह {{math|{''b''} }} और स्वतंत्र समूह {{math|{''a'', ''c''} }}

विभक्त ग्राफ़ को उनके निषिद्ध प्रेरित उप-अनुच्छेदों के संदर्भ में वर्णित किया जा सकता है। यदि ग्राफ विभाजित होता है और यदि कोई [[प्रेरित सबग्राफ]] चार या पांच शिखर पर [[चक्र ग्राफ]] नहीं होता है और भिन्न-भिन्न किनारों की जोड़ी (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>

चूँकि कॉर्डल ग्राफ़ पूर्ण ग्राफ़ होते हैं, इसलिए यह विभाजित ग्राफ़ भी होते हैं। दोगुना विभक्त ग्राफ़ प्रत्येक कोने को दोगुना करके विभक्त ग्राफ़ से प्राप्त ग्राफ़ का समूह (इसलिए क्लिक मिलान को प्रेरित करने के लिए और स्वतंत्र समूह मिलान को प्रेरित करने के लिए आता है), प्रमुख रूप से [[सही ग्राफ]]<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>

ये तिरछे मर्ज किए गए क्रमपरिवर्तन के क्रमपरिवर्तन ग्राफ़ हैं।{{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|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|i}} अधिकतम स्वतंत्र समुच्चय है। इस स्थिति में, {{mvar|G}} का विशिष्ट विभाजन {{math|(''C'', ''i'')}} समूह और स्वतंत्र समूह में है, {{mvar|C}} अधिकतम क्लिक है, और {{mvar|i}} अधिकतम स्वतंत्र समूह है।

कुछ अन्य अनुकूलन समस्याएं जो अधिक सामान्य ग्राफ़ समूहों पर एनपी-पूर्ण हैं। [[ग्राफ रंग]] सहित, विभाजित ग्राफ़ पर समान रूप से सीधी हैं। [[हैमिल्टनियन चक्र]] खोजना एनपी-पूर्ण रहता है। यहां तक कि विभाजित ग्राफ के लिए भी जो दृढ़ता से कॉर्डल ग्राफ होते हैं।<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}} विभाजित ग्राफ है। यदि,
:<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>

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

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

==टिप्पणियाँ==
{{reflist|30em}}


==संदर्भ==
{{refbegin|30em}}
*{{citation
 | last1 = Bender | first1 = E. A.
 | last2 = Richmond | first2 = L. B.
 | last3 = Wormald | first3 = N. C.
 | title = Almost all chordal graphs split
 | journal = J. Austral. Math. Soc.
 | series = A
 | volume = 38
 | year = 1985
 | issue = 2
 | mr = 0770128
 | pages = 214–221
 | doi = 10.1017/S1446788700023077| doi-access = free
 }}.
*{{citation
 | last = Bertossi | first = Alan A.
 | title = Dominating sets for split and bipartite graphs
 | journal = [[Information Processing Letters]]
 | volume = 19
 | year = 1984
 | pages = 37–40
 | doi=10.1016/0020-0190(84)90126-1
}}.
*{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 0-89871-432-X
 | url-access = registration
 | url = https://archive.org/details/graphclassessurv0000bran
 }}.
*{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | title = The strong perfect graph theorem
 | journal = [[Annals of Mathematics]]
 | volume = 164
 | year = 2006
 | issue = 1
 | pages = 51–229
 | mr = 2233847
 | doi = 10.4007/annals.2006.164.51| arxiv = math/0212070}}.
*{{citation
 | last1 = Földes | first1 = Stéphane
 | last2 = Hammer | first2 = Peter Ladislaw | author2-link =Peter Ladislaw Hammer
 | contribution = Split graphs
 | title = Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
 | pages = 311–315
 | series = Congressus Numerantium
 | volume = XIX
 | publisher = Utilitas Math.
 | location = Winnipeg
 | year = 1977a
 | mr = 0505860}}.
*{{citation
 | last1 = Földes | first1 = Stéphane
 | last2 = Hammer | first2 = Peter Ladislaw | author2-link =Peter Ladislaw Hammer
 | title = Split graphs having Dilworth number two
 | journal = [[Canadian Journal of Mathematics]]
 | volume = 29
 | year = 1977b
 | issue = 3
 | pages = 666–672
 | mr = 0463041
 | doi = 10.4153/CJM-1977-069-1}}.
*{{citation
 | last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
 | title = Algorithmic Graph Theory and Perfect Graphs
 | publisher = Academic Press
 | year = 1980
 | isbn = 0-12-289260-7
 | mr = 0562306}}.
*{{citation
 | last1 = Hammer | first1 = Peter Ladislaw | author1-link = Peter Ladislaw Hammer
 | last2 = Simeone | first2 = Bruno
 | title = The splittance of a graph
 | journal = [[Combinatorica]]
 | volume = 1
 | year = 1981
 | issue = 3
 | pages = 275–284
 | mr = 0637832
 | doi = 10.1007/BF02579333}}.
*{{citation
 | last1 = Kézdy | first1 = André E.
 | last2 = Snevily | first2 = Hunter S.
 | last3 = Wang | first3 = Chi
 | doi = 10.1016/S0097-3165(96)80012-4
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]], Series A
 | mr = 1370138
 | pages = 353–359
 | title = Partitioning permutations into increasing and decreasing subsequences
 | volume = 73
 | year = 1996| doi-access = free
 }}.
*{{citation
 | last1 = McMorris | first1 = F. R.
 | last2 = Shier | first2 = D. R.
 | title = Representing chordal graphs on ''K''<sub>1,''n''</sub>
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 24
 | year = 1983
 | pages = 489–494
 | mr = 0730144}}.
*{{citation
 | last = Merris | first = Russell
 | title = Split graphs
 | journal = [[European Journal of Combinatorics]]
 | volume = 24
 | year = 2003
 | issue = 4
 | pages = 413–430
 | doi = 10.1016/S0195-6698(03)00030-1
 | mr = 1975945| doi-access = free
 }}.
*{{citation
 | last = Müller | first = Haiko
 | title = Hamiltonian Circuits in Chordal Bipartite Graphs
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 156
 | year = 1996
 | pages = 291–298
 | doi=10.1016/0012-365x(95)00057-4
| doi-access = free
 }}.
*{{citation
 | last = Royle | first = Gordon F. | authorlink = Gordon Royle
 | title = Counting set covers and split graphs
 | journal = Journal of Integer Sequences
 | volume = 3
 | year = 2000
 | issue = 2
 | pages = 00.2.6
 | mr = 1778996
 | url = http://www.emis.de/journals/JIS/VOL3/ROYLE/royle.pdf}}.
*{{Citation
 | last = Tyshkevich | first = Regina I. | authorlink=Regina Tyshkevich
 | title = [The canonical decomposition of a graph]
 | language = Russian
 | journal = [[Doklady Akademii Nauk SSSR]]
 | volume = 24
 | year = 1980
 | pages = 677–679
 | mr = 0587712}}
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Chernyak | first2 = A. A.
 | title = Canonical partition of a graph defined by the degrees of its vertices
 | language = Russian
 | year = 1979
 | journal = Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk
 | volume = 5
 | pages = 14–26
 | mr = 0554162}}.
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Chernyak | first2 = A. A.
 | script-title=ru:Еще один метод перечисления непомеченных комбинаторных объектов
 | language = Russian
 | year = 1990
 | journal = Mat. Zametki
 | volume = 48
 | pages = 98–105
 | mr = 1102626
 | url = http://mi.mathnet.ru/eng/mz3413
 | issue = 6}}. 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}}.
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Melnikow | first2 = O. I.
 | last3 = Kotov | first3 = V. M.
 | title = On graphs and degree sequences: the canonical decomposition
 | language = Russian
 | journal = Kibernetika
 | volume = 6
 | year = 1981
 | pages = 5–8
 | mr = 0689420}}.
*{{citation
 | last = Voss | first = H.-J.
 | title = Note on a paper of McMorris and Shier
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 26
 | year = 1985
 | pages = 319–322
 | mr = 0803929}}.
{{refend}}


==अग्रिम पठन==
*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:Created On 28/02/2023]]