द्विदलीय ग्राफ: Difference between revisions

[[File:Biclique K 3 5 bicolor.svg|thumbnail|एम = 5 और एन = 3 के साथ [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विभाज्य ग्राफ]]]]

[[File:Heawood graph bipartite (bicolor).svg|thumb|[[हेवुड ग्राफ]] द्विभाज्य है।]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, '''द्विभाज्य ग्राफ''' (या '''बिग्राफ''') एक ऐसा ग्राफ (असतत गणित) है जिसके शीर्षों (ग्राफ सिद्धांत) को दो [[असंयुक्त सेट|असंयुक्त समुच्चय]] और स्वतंत्र समुच्चय (ग्राफ सिद्धांत) <math>U</math> और <math>V</math> में विभाजित किया जा सकता है। अर्थात्, प्रत्येक [[किनारा (ग्राफ़ सिद्धांत)|वर्टेक्स (ग्राफ़ सिद्धांत)]] <math>U</math> में एक शीर्ष को <math>V</math> में एक से जोड़ता है। वर्टेक्स समुच्चय <math>U</math> और <math>V</math> को सामान्यतः ग्राफ़ के भाग कहा जाता है। समान रूप से, एक द्विभाज्य ग्राफ ऐसा ग्राफ है जिसमें कोई विषम-लंबाई [[चक्र (ग्राफ सिद्धांत)]] नहीं होता है।<ref name=diestel2005graph>{{citation|last=Diestel|first=Reinard|title=Graph Theory|series=[[Graduate Texts in Mathematics]]|year=2005|publisher=Springer|isbn=978-3-642-14278-9|url=http://diestel-graph-theory.com/|access-date=2012-02-27|archive-date=2011-04-09|archive-url=https://web.archive.org/web/20110409144253/http://diestel-graph-theory.com/|url-status=live}}</ref><ref>{{citation

एक द्विभाज्य ग्राफ़ को दर्शाने के लिए अधिकांश <math>G=(U,V,E)</math> लिखा जाता है जिसके विभाजन में <math>U</math> और <math>V</math> भाग होते हैं, <math>E</math> ग्राफ़ के किनारों को दर्शाता है। यदि एक द्विभाज्य ग्राफ [[जुड़ा हुआ ग्राफ़]] नहीं है, तो इसमें से अधिक द्विविभाजन हो सकते हैं;<ref>{{citation

  | year = 2008}}.</ref> इस स्थिति में, <math>(U,V,E)</math> नोटेशन एक विशेष द्विविभाजन को निर्दिष्ट करने में सहायक होता है जो किसी अनुप्रयोग में महत्वपूर्ण हो सकता है। यदि <math>|U|=|V|</math>, अर्थात, यदि दो उपसमुच्चयों में समान [[प्रमुखता|कार्डिनैलिटी]] है, तो <math>G</math> को संतुलित द्विभाज्य ग्राफ कहा जाता है।<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> यदि द्विविभाजन के एक ही तरफ के सभी शीर्षों की [[डिग्री (ग्राफ सिद्धांत)]] समान है, तो <math>G</math> द्विविभाजन ग्राफ कहलाता है।

जब वस्तुओं के दो भिन्न-भिन्न वर्गों के बीच [[विषम संबंध]] मॉडलिंग करते हैं, तो द्विभाज्य ग्राफ़ अधिकांश प्राकृतिक रूप से उत्पन्न होते हैं। उदाहरण के लिए, फुटबॉल खिलाड़ियों और क्लबों का ग्राफ, एक खिलाड़ी और एक क्लब के बीच बढ़त के साथ, यदि खिलाड़ी उस क्लब के लिए खेला है, तो यह संबद्धता नेटवर्क का प्राकृतिक उदाहरण है, जो [[सामाजिक नेटवर्क विश्लेषण]] में उपयोग किया जाने वाला प्रकार का द्विभाज्य ग्राफ है।<ref>{{citation

तीसरा उदाहरण मुद्राशास्त्र के शैक्षणिक क्षेत्र में है। प्राचीन सिक्के डिज़ाइन के दो धनात्मक प्रभावों (सामने और पीछे) का उपयोग करके बनाए जाते हैं। मुद्राशास्त्री सिक्कों के उत्पादन को दर्शाने के लिए जो चार्ट बनाते हैं, वे द्विभाज्य ग्राफ होते हैं।<ref name="bracey2012">{{citation|last=Bracey|first=Robert|editor1-first=David M.|editor1-last=Jacobson|editor2-first=Nikos|editor2-last=Kokkinos|chapter=On the graphical interpretation of Herod's year 3 coins|title=Judaea and Rome in Coins 65 BCE – 135 CE: Papers Presented at the International Conference hosted by Spink, 13th – 14th September 2010|year=2012|publisher=[[Spink & Son]]|pages=65–84}}</ref>

*सम संख्या में शीर्षों वाले [[ चक्र ग्राफ | चक्र ग्राफ]] द्विभाज्य होते हैं।<ref name="s12" />

*प्रत्येक [[समतलीय ग्राफ]], जिसके सभी फलकों की लंबाई सम है, द्विभाज्य है।<ref>{{citation|first=Alexander|last=Soifer|author-link=Alexander Soifer|year=2008|title=The Mathematical Coloring Book|title-link= The Mathematical Coloring Book |publisher=Springer-Verlag|isbn=978-0-387-74640-1|pages=136–137}}. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of [[Alfred Kempe]] containing a false proof of the [[four color theorem]].</ref> इसके विशेष स्थिति [[ग्रिड ग्राफ]] और [[वर्गाकार|वर्गाकार ग्राफ़]] हैं, जिनमें प्रत्येक आंतरिक फलक में 4 किनारे होते हैं और प्रत्येक आंतरिक शीर्ष पर चार या अधिक पड़ोसी होते हैं।<ref>{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=[[SIAM Journal on Discrete Mathematics]]|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301|s2cid=10788524}}.</ref>

* ''m'' और ''n'' शीर्षों पर पूर्ण द्विभाज्य ग्राफ, जिसे ''K_n,m'' द्वारा निरूपित किया जाता है, द्विभाज्य ग्राफ <math>G = (U, V, E)</math> है, जहां U और V क्रमशः m और n आकार के असंयुक्त समुच्चय हैं, और E, U के प्रत्येक शीर्ष को V के सभी शीर्षों से जोड़ता है। यह इस प्रकार है कि ''K_m,n'' ''mn'' किनारे हैं।<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> पूर्ण द्विभाज्य ग्राफ से निकटता से संबंधित [[ ताज ग्राफ | क्राउन ग्राफ़]] हैं, जो पूर्ण मिलान के किनारों को हटाकर पूर्ण द्विभाज्य ग्राफ से बनते हैं।<ref>{{citation

*[[हाइपरक्यूब ग्राफ]], आंशिक क्यूब्स और [[माध्यिका ग्राफ]] द्विभाज्य हैं। इन ग्राफ़ों में, शीर्षों को [[बिटवेक्टर|बिटवेक्टरों]] द्वारा इस प्रकार से लेबल किया जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल यदि संबंधित बिटवेक्टर ही स्थिति में भिन्न हों। उन शीर्षों को अलग करके द्विविभाजन बनाया जा सकता है जिनके बिटवेक्टर में विषम संख्या वाले शीर्षों से इकाइयों की संख्या सम है। ट्री और वर्गालेख माध्यिका ग्राफ़ के उदाहरण बनाते हैं, और प्रत्येक माध्यिका ग्राफ़ [[आंशिक घन]] है।<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>

द्विभाज्य ग्राफ को कई भिन्न-भिन्न विधियों से चित्रित किया जा सकता है:

*ग्राफ द्विभाज्य होता है यदि और केवल यदि प्रत्येक वर्टेक्स विषम संख्या में [[कट (ग्राफ सिद्धांत)]] से संबंधित हो, किनारों के न्यूनतम उपग्राफ जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।<ref>{{citation

===कोनिग का प्रमेय और पूर्ण ग्राफ===

द्विभाज्य ग्राफ में, [[न्यूनतम शीर्ष कवर]] का आकार [[अधिकतम मिलान]] के आकार के समान होता है; यह कोनिग का प्रमेय (ग्राफ सिद्धांत) है।<ref>{{citation

  | year = 2005}}.</ref> इस प्रमेय का एक वैकल्पिक और समतुल्य रूप यह है कि [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समुच्चय]] का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के समान है। [[पृथक शीर्ष]] के बिना किसी भी ग्राफ़ में न्यूनतम किनारे कवर का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के समान होता है।<ref>{{citation

  | year = 2012}}.</ref> इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, द्विभाज्य ग्राफ में, न्यूनतम किनारे कवर का आकार अधिकतम स्वतंत्र समुच्चय के आकार के समान होता है, और न्यूनतम किनारे कवर का आकार और न्यूनतम शीर्ष कवर का आकार शीर्षों की संख्या के समान होता है।

संबंधित परिणामों का एक अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विभाज्य ग्राफ, प्रत्येक द्विभाज्य ग्राफ का [[पूरक (ग्राफ सिद्धांत)]], प्रत्येक द्विभाज्य ग्राफ का रेखा ग्राफ़, और प्रत्येक द्विभाज्य ग्राफ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विभाज्य ग्राफ की पूर्णता देखना (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) आसान है किन्तु द्विभाज्य ग्राफ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का और पुनर्कथन है। यह उन परिणामों में से एक था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया था।<ref>{{citation|title=Modern Graph Theory

|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> पूर्ण ग्राफ़ के लाइन ग्राफ़ के पूरकों की पूर्णता कोनिग के प्रमेय का और पुनर्कथन है, और लाइन ग्राफ़ की पूर्णता स्वयं कोनिग के पहले के प्रमेय का पुनर्कथन है, कि प्रत्येक द्विभाज्य ग्राफ में अधिकतम डिग्री के बराबर रंगों की संख्या का उपयोग करके एक [[किनारे का रंग]] होता है।

[[मजबूत परफेक्ट ग्राफ प्रमेय]] के अनुसार, परफेक्ट ग्राफ में द्विभाज्य ग्राफ के समान [[निषिद्ध ग्राफ लक्षण वर्णन]] होता है: ग्राफ द्विभाज्य होता है यदि और केवल यदि इसमें उपग्राफ के रूप में कोई विषम चक्र नहीं होता है, और एक ग्राफ तभी सही होता है जब इसमें कोई विषम चक्र नहीं होता है या एक प्रेरित उपग्राफ के रूप में इसका पूरक (ग्राफ़ सिद्धांत) नहीं होता है। द्विभाज्य ग्राफ, द्विभाज्य ग्राफ के रेखा ग्राफ़, और उनके पूरक मजबूत पूर्ण ग्राफ़ प्रमेय के प्रमाण में उपयोग किए जाने वाले पूर्ण ग्राफ़ के पांच मूलभूत वर्गों में से चार बनाते हैं।<ref>{{citation

द्विभाज्य ग्राफ का डिग्री अनुक्रम सूचियों की जोड़ी है जिसमें प्रत्येक में दो भागों <math>U</math> और <math>V</math> की डिग्री होती है। उदाहरण के लिए, पूर्ण द्विभाज्य ग्राफ K_3,5 में डिग्री अनुक्रम <math>(5,5,5),(3,3,3,3,3)</math> होता है। आइसोमोर्फिक द्विभाज्य ग्राफ़ में समान डिग्री अनुक्रम होता है। चूँकि, डिग्री अनुक्रम, सामान्यतः, विशिष्ट रूप से एक द्विभाज्य ग्राफ की पहचान नहीं करता है; कुछ स्थितियों में, गैर-आइसोमोर्फिक द्विभाज्य ग्राफ़ में समान डिग्री अनुक्रम हो सकता है।

द्विभाज्य बोध समस्या प्राकृतिक संख्याओं की दो दी गई सूचियों के डिग्री अनुक्रम के साथ सरल द्विभाज्य ग्राफ खोजने की समस्या है। (अनुगामी शून्यों को नजरअंदाज किया जा सकता है क्योंकि उन्हें डिग्राफ में उचित संख्या में पृथक शीर्षों को जोड़कर तुच्छ रूप से अनुभव किया जाता है।)

===हाइपरग्राफ और निर्देशित ग्राफ से संबंध===

द्विभाज्य ग्राफ <math>(U,V,E)</math> का द्विआसन्नता मैट्रिक्स <math>|U|\times|V|</math> आकार का एक (0,1) मैट्रिक्स है। इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए एक और गैर-आसन्न शीर्षों के लिए एक शून्य है।<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> द्विभाज्य ग्राफ़, [[हाइपरग्राफ]] और निर्देशित ग्राफ़ के बीच समानता का वर्णन करने के लिए द्विआसन्नता मैट्रिक्स का उपयोग किया जा सकता है।।

हाइपरग्राफ एक संयोजी संरचना है, जिसमें एक अप्रत्यक्ष ग्राफ की तरह, शीर्ष और किनारे होते हैं, लेकिन जिसमें किनारों में बिल्कुल दो समापन बिंदु होने के बजाय शीर्षों का स्वैच्छिक सेट हो सकता है। हाइपरग्राफ को मॉडल करने के लिए एक द्विभाज्य ग्राफ <math>(U,V,E)</math> का उपयोग किया जा सकता है जिसमें {{mvar|U}} हाइपरग्राफ के शीर्षों का सेट है, {{mvar|V}} हाइपरएज का सेट है, और {{mvar|E}} में हाइपरग्राफ वर्टेक्स {{mvar|v}} से हाइपरग्राफ किनारे {{mvar|e}} तक एक किनारा होता है, ठीक उसी समय जब {{mvar|v}} {{mvar|e}} के अंतिम बिंदुओं में से एक होता है। इस पत्राचार के अनुसार, द्विभाज्य ग्राफ के द्विआसन्नता मैट्रिक्स वास्तव में संबंधित हाइपरग्राफ के [[घटना मैट्रिक्स]] हैं। द्विभाज्य ग्राफ और हाइपरग्राफ के बीच इस पत्राचार के विशेष स्थिति के रूप में, किसी भी [[मल्टीग्राफ]] (ग्राफ जिसमें समान दो शीर्षों के बीच दो या दो से अधिक किनारे हो सकते हैं) को हाइपरग्राफ के रूप में व्याख्या किया जा सकता है जिसमें कुछ हाइपरएज में समापन बिंदुओं के समान समुच्चय होते हैं, और द्विभाज्य ग्राफ द्वारा दर्शाया गया है जिसमें एकाधिक आसन्नताएं नहीं होती हैं और जिसमें द्विविभाजन के एक तरफ सभी कोने में डिग्री दो होती है।<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>

निकटवर्ती मैट्रिक्स की समान पुनर्व्याख्या का उपयोग [[निर्देशित ग्राफ]] (लेबल वाले शीर्षों की दी गई संख्या पर, स्व-लूप की अनुमति) और संतुलित द्विभाज्य ग्राफ के बीच एक-से-पत्राचार दिखाने के लिए किया जा सकता है, जिसमें द्विविभाजन के दोनों किनारों पर समान संख्या में कोने होते हैं। क्योंकि, {{mvar|n}} शीर्षों के साथ एक निर्देशित ग्राफ का आसन्न मैट्रिक्स <math>n\times n</math> आकार का कोई भी (0,1) मैट्रिक्स हो सकता है, जिसे उसके द्विविभाजन के प्रत्येक पक्ष पर {{mvar|n}} शीर्षों के साथ एक द्विभाज्य ग्राफ के आसन्न मैट्रिक्स के रूप में पुन: व्याख्या किया जा सकता है।<ref>{{citation

  }}.</ref> इस निर्माण में, द्विभाज्य ग्राफ निर्देशित ग्राफ का [[द्विदलीय दोहरा आवरण|द्विभाज्य दोहरा आवरण]] है।

यह परीक्षण करना संभव है कि क्या कोई ग्राफ द्विभाज्य है, और [[गहराई-पहली खोज|डेप्थ-फर्स्ट सर्च]] का उपयोग करके, [[रैखिक समय]] में तो दो-रंग (यदि यह द्विभाज्य है) या एक विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो डेप्थ-फर्स्ट सर्च फारेस्ट में उसके मूल रंग से भिन्न हो, डेप्थ-फर्स्ट-सर्च फारेस्ट के [[प्रीऑर्डर ट्रैवर्सल]] में रंग निर्दिष्ट किया जाए। यह आवश्यक रूप से फैले हुए फारेस्ट को दो-रंग प्रदान करेगा जिसमें शीर्षों को उनके पैरेंट्स से जोड़ने वाले किनारे सम्मिलित होंगे, किन्तु यह कुछ नॉन-फारेस्ट किनारों को ठीक से रंग नहीं सकता है। डेप्थ-फर्स्ट सर्च फारेस्ट में, प्रत्येक नॉन-फारेस्ट किनारे के दो समापन बिंदुओं में से दूसरे समापन बिंदु का एन्सेस्टर होता है, और जब डेप्थ की फर्स्ट सर्च इस प्रकार के किनारे की सर्च करती है तो उसे जांचना चाहिए कि इन दोनों शीर्षों के भिन्न-भिन्न रंग हैं। यदि वे ऐसा नहीं करते हैं, तो फारेस्ट में एन्सेस्टर से डिसेंडेंट्स तक का पथ, डिसकलर किनारे के साथ, विषम चक्र बनाता है, जिसे एल्गोरिदम से इस परिणाम के साथ लौटाया जाता है कि ग्राफ द्विभाज्य नहीं है। चूँकि, यदि एल्गोरिथ्म इस प्रकार के विषम चक्र का पता लगाए बिना समाप्त हो जाता है, तो प्रत्येक किनारे को उचित रूप से रंगीन होना चाहिए, और एल्गोरिथ्म रंग को इस परिणाम के साथ लौटाता है कि ग्राफ द्विभाज्य है।<ref>{{citation

वैकल्पिक रूप से, समान प्रक्रिया का उपयोग डेप्थ-फर्स्ट सर्च के स्थान पर ब्रेड्थ-फर्स्ट सर्च के साथ किया जा सकता है। पुनः, प्रत्येक नोड को ब्रेड्थ-फर्स्ट क्रम में, सर्च फारेस्ट में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से �