द्विदलीय ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
Line 6: | Line 6: | ||
| footer = Example of a bipartite graph without cycles | | footer = Example of a bipartite graph without cycles | ||
}} | }} | ||
[[File:Biclique K 3 5 bicolor.svg|thumbnail|एम = 5 और एन = 3 के साथ [[पूर्ण द्विदलीय ग्राफ]]]] | [[File:Biclique K 3 5 bicolor.svg|thumbnail|एम = 5 और एन = 3 के साथ [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विभाज्य ग्राफ]]]] | ||
[[File:Heawood graph bipartite (bicolor).svg|thumb|[[हेवुड ग्राफ]] | [[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 | ||
| last1 = Asratian | | last1 = Asratian | ||
| first1 = Armen S. | | first1 = Armen S. | ||
Line 23: | Line 23: | ||
| url = https://archive.org/details/bipartitegraphst0000asra | | url = https://archive.org/details/bipartitegraphst0000asra | ||
}}.</ref> | }}.</ref> | ||
दो | दो समुच्चय <math>U</math> और <math>V</math> इसे ग्राफ़ को दो रंगों से रंगने के रूप में सोचा जा सकता है: यदि कोई सभी नोड्स को <math>U</math> नीले रंग में रंगता है, और सभी नोड्स को <math>V</math> लाल रंग में रंगता है, तो प्रत्येक किनारे पर अलग-अलग रंगों के समापन बिंदु होते हैं, जैसा कि ग्राफ़ रंग समस्या में आवश्यक है।<ref name="adh98-7"/><ref name="s12">{{citation | ||
| last = Scheinerman | first = Edward R. | author-link = Ed Scheinerman | | last = Scheinerman | first = Edward R. | author-link = Ed Scheinerman | ||
| edition = 3rd | | edition = 3rd | ||
Line 31: | Line 31: | ||
| title = Mathematics: A Discrete Introduction | | title = Mathematics: A Discrete Introduction | ||
| url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363 | | url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363 | ||
| year = 2012}}.</ref> इसके विपरीत, गैर-द्विपक्षीय ग्राफ़ के | | year = 2012}}.</ref> इसके विपरीत, गैर-द्विपक्षीय ग्राफ़ के स्थिति में ऐसा रंग असंभव है, जैसे कि [[नामित ग्राफ़ की गैलरी|त्रिकोण]]: एक नोड को नीला और दूसरे को लाल रंग देने के बाद, त्रिकोण का तीसरा शीर्ष दोनों रंगों के शीर्षों से जुड़ा होता है, जिससे इसे किसी भी रंग को निर्दिष्ट करने से रोका जा सकता है। | ||
एक द्विभाज्य ग्राफ़ को दर्शाने के लिए अधिकांश <math>G=(U,V,E)</math> लिखा जाता है जिसके विभाजन में <math>U</math> और <math>V</math> भाग होते हैं, <math>E</math> ग्राफ़ के किनारों को दर्शाता है। यदि एक द्विभाज्य ग्राफ [[जुड़ा हुआ ग्राफ़]] नहीं है, तो इसमें से अधिक द्विविभाजन हो सकते हैं;<ref>{{citation | |||
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand | | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand | ||
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist) | | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist) | ||
Line 43: | Line 43: | ||
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223 | | url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223 | ||
| volume = 53 | | volume = 53 | ||
| year = 2008}}.</ref> इस | | 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 | ||
| last1 = Wasserman | first1 = Stanley | | last1 = Wasserman | first1 = Stanley | ||
| author-link1= Stanley Wasserman | | author-link1= Stanley Wasserman | ||
Line 59: | Line 59: | ||
| volume = 8 | | volume = 8 | ||
| year = 1994}}.</ref> | | year = 1994}}.</ref> | ||
अन्य उदाहरण जहां | अन्य उदाहरण जहां द्विभाज्य ग्राफ स्वाभाविक रूप से दिखाई देते हैं वह (एनपी-पूर्ण) रेलवे अनुकूलन समस्या है, जिसमें इनपुट ट्रेनों और उनके स्टॉप का शेड्यूल है, और लक्ष्य ट्रेन स्टेशनों का समुच्चय जितना संभव हो उतना छोटा ढूंढना है ताकि प्रत्येक ट्रेन चुने गए स्टेशनों में से कम से कम पर जाती है। इस समस्या को द्विभाज्य ग्राफ में प्रमुख समुच्चय समस्या के रूप में तैयार किया जा सकता है जिसमें प्रत्येक ट्रेन और प्रत्येक स्टेशन के लिए शीर्ष होता है और स्टेशन और उस स्टेशन पर रुकने वाली ट्रेन के प्रत्येक जोड़े के लिए वर्टेक्स होता है।<ref name=niedermeier2006invitiation>{{citation|last=Niedermeier|first=Rolf|author-link=Rolf Niedermeier|title=Invitation to Fixed Parameter Algorithms|series=Oxford Lecture Series in Mathematics and Its Applications|year=2006|publisher=Oxford University Press|isbn=978-0-19-856607-6|pages=20–21}}</ref> | ||
तीसरा उदाहरण मुद्राशास्त्र के शैक्षणिक क्षेत्र में है। प्राचीन सिक्के डिज़ाइन के दो सकारात्मक प्रभावों (सामने और पीछे) का उपयोग करके बनाए जाते हैं। मुद्राशास्त्री सिक्कों के उत्पादन को दर्शाने के लिए जो चार्ट बनाते हैं, वे | तीसरा उदाहरण मुद्राशास्त्र के शैक्षणिक क्षेत्र में है। प्राचीन सिक्के डिज़ाइन के दो सकारात्मक प्रभावों (सामने और पीछे) का उपयोग करके बनाए जाते हैं। मुद्राशास्त्री सिक्कों के उत्पादन को दर्शाने के लिए जो चार्ट बनाते हैं, वे द्विभाज्य ग्राफ होते हैं।<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 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> | ||
* एम और एन शीर्षों पर पूर्ण | * एम और एन शीर्षों पर पूर्ण द्विभाज्य ग्राफ, के द्वारा निरूपित<sub>n,m</sub>द्विदलीय ग्राफ है <math>G = (U, V, E)</math>, जहां U और V क्रमशः m और n आकार के असंयुक्त समुच्चय हैं, और E, U के प्रत्येक शीर्ष को V के सभी शीर्षों से जोड़ता है। यह इस प्रकार है कि K<sub>m,n</sub>एमएन किनारे हैं।<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> पूर्ण द्विभाज्य ग्राफ से निकटता से संबंधित [[ ताज ग्राफ ]]़ हैं, जो पूर्ण मिलान के किनारों को हटाकर पूर्ण द्विभाज्य ग्राफ से बनते हैं।<ref>{{citation | ||
| last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon | | last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon | ||
| last2 = Debowsky | first2 = M. | | last2 = Debowsky | first2 = M. | ||
Line 76: | Line 76: | ||
| year = 2004| doi-access = free | | year = 2004| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
* [[हाइपरक्यूब ग्राफ]]़, आंशिक क्यूब्स और [[माध्यिका ग्राफ]]़ | * [[हाइपरक्यूब ग्राफ]]़, आंशिक क्यूब्स और [[माध्यिका ग्राफ]]़ द्विभाज्य हैं। इन ग्राफ़ों में, शीर्षों को [[बिटवेक्टर]]ों द्वारा इस तरह से लेबल किया जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल यदि संबंधित बिटवेक्टर ही स्थिति में भिन्न हों। उन शीर्षों को अलग करके द्विविभाजन बनाया जा सकता है जिनके बिटवेक्टर में विषम संख्या वाले शीर्षों से इकाइयों की संख्या सम है। पेड़ और वर्गालेख माध्यिका ग्राफ़ के उदाहरण बनाते हैं, और प्रत्येक माध्यिका ग्राफ़ [[आंशिक घन]] है।<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> | ||
Line 82: | Line 82: | ||
===लक्षणीकरण=== | ===लक्षणीकरण=== | ||
द्विभाज्य ग्राफ को कई अलग-अलग तरीकों से चित्रित किया जा सकता है: | |||
* अप्रत्यक्ष ग्राफ़ | * अप्रत्यक्ष ग्राफ़ द्विभाज्य है यदि और केवल तभी जब इसमें कोई चक्र (ग्राफ़ सिद्धांत) शामिल न हो।<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [[Dénes Kőnig]]. For infinite graphs, this result requires the [[axiom of choice]].</ref><ref>{{citation | ||
| last1 = Bang-Jensen | | last1 = Bang-Jensen | ||
| first1 = Jørgen | | first1 = Jørgen | ||
Line 99: | Line 99: | ||
| url-status = live | | url-status = live | ||
}}</ref> | }}</ref> | ||
* ग्राफ़ | * ग्राफ़ द्विभाज्य है यदि और केवल यदि वह 2-रंगीय है, (अर्थात इसकी वर्णिक संख्या 2 से कम या उसके बराबर है)।<ref name="adh98-7"/>* ग्राफ द्विभाज्य होता है यदि और केवल यदि प्रत्येक वर्टेक्स विषम संख्या में [[कट (ग्राफ सिद्धांत)]] से संबंधित हो, किनारों के न्यूनतम उपसमूह जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।<ref>{{citation | ||
| last = Woodall | first = D. R. | | last = Woodall | first = D. R. | ||
| doi = 10.1016/0012-365X(90)90380-Z | | doi = 10.1016/0012-365X(90)90380-Z | ||
Line 109: | Line 109: | ||
| volume = 84 | | volume = 84 | ||
| year = 1990| doi-access = free | | year = 1990| doi-access = free | ||
}}</ref> * ग्राफ़ | }}</ref> * ग्राफ़ द्विभाज्य है यदि और केवल यदि ग्राफ़ का वर्णक्रमीय ग्राफ़ सिद्धांत सममित है।<ref>{{citation | ||
| last = Biggs | first = Norman | | last = Biggs | first = Norman | ||
| edition = 2nd | | edition = 2nd | ||
Line 122: | Line 122: | ||
===कोनिग का प्रमेय और पूर्ण ग्राफ=== | ===कोनिग का प्रमेय और पूर्ण ग्राफ=== | ||
द्विभाज्य ग्राफ में, [[न्यूनतम शीर्ष कवर]] का आकार [[अधिकतम मिलान]] के आकार के बराबर होता है; यह कोनिग का प्रमेय (ग्राफ सिद्धांत) है|कोनिग का प्रमेय।<ref>{{citation | |||
| author = Kőnig, Dénes | | author = Kőnig, Dénes | ||
| author-link = Dénes Kőnig | | author-link = Dénes Kőnig | ||
Line 139: | Line 139: | ||
| title = Graph Theory and Its Applications | | title = Graph Theory and Its Applications | ||
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568 | ||
| year = 2005}}.</ref> इस प्रमेय का वैकल्पिक और समतुल्य रूप यह है कि [[अधिकतम स्वतंत्र सेट]] का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर है। [[पृथक शीर्ष]] के बिना किसी भी ग्राफ़ में न्यूनतम किनारे कवर का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर होता है।<ref>{{citation | | year = 2005}}.</ref> इस प्रमेय का वैकल्पिक और समतुल्य रूप यह है कि [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समुच्चय]] का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर है। [[पृथक शीर्ष]] के बिना किसी भी ग्राफ़ में न्यूनतम किनारे कवर का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर होता है।<ref>{{citation | ||
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand | | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand | ||
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist) | | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist) | ||
Line 147: | Line 147: | ||
| title = A First Course in Graph Theory | | title = A First Course in Graph Theory | ||
| url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | | url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189 | ||
| year = 2012}}.</ref> इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, | | year = 2012}}.</ref> इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, द्विभाज्य ग्राफ में, न्यूनतम किनारे कवर का आकार अधिकतम स्वतंत्र समुच्चय के आकार के बराबर होता है, और न्यूनतम किनारे कवर का आकार और न्यूनतम शीर्ष कवर का आकार होता है शीर्षों की संख्या के बराबर है. | ||
संबंधित परिणामों का अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक | संबंधित परिणामों का अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विभाज्य ग्राफ, प्रत्येक द्विभाज्य ग्राफ का [[पूरक (ग्राफ सिद्धांत)]], प्रत्येक द्विभाज्य ग्राफ का रेखा ग्राफ़, और प्रत्येक द्विभाज्य ग्राफ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विभाज्य ग्राफ की पूर्णता देखना आसान है (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) लेकिन द्विभाज्य ग्राफ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का और पुनर्कथन है। यह उन परिणामों में से था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया।<ref>{{citation|title=Modern Graph Theory | ||
|volume= 184 |series= Graduate Texts in Mathematics | |volume= 184 |series= Graduate Texts in Mathematics | ||
|author=Béla Bollobás|publisher =Springer|year= 1998 | |author=Béla Bollobás|publisher =Springer|year= 1998 | ||
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> पूर्ण ग्राफ़ के लाइन ग्राफ़ के पूरकों की पूर्णता कोनिग के प्रमेय का और पुनर्कथन है, और लाइन ग्राफ़ की पूर्णता स्वयं कोनिग के पहले के प्रमेय का पुनर्कथन है, कि प्रत्येक | |isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> पूर्ण ग्राफ़ के लाइन ग्राफ़ के पूरकों की पूर्णता कोनिग के प्रमेय का और पुनर्कथन है, और लाइन ग्राफ़ की पूर्णता स्वयं कोनिग के पहले के प्रमेय का पुनर्कथन है, कि प्रत्येक द्विभाज्य ग्राफ में कई रंगों का उपयोग करके [[किनारे का रंग]] होता है इसकी अधिकतम डिग्री. | ||
[[मजबूत परफेक्ट ग्राफ प्रमेय]] के अनुसार, परफेक्ट ग्राफ में | [[मजबूत परफेक्ट ग्राफ प्रमेय]] के अनुसार, परफेक्ट ग्राफ में द्विभाज्य ग्राफ के समान [[निषिद्ध ग्राफ लक्षण वर्णन]] होता है: ग्राफ द्विभाज्य होता है यदि और केवल तभी जब इसमें सबग्राफ के रूप में कोई विषम चक्र न हो, और ग्राफ तभी सही होता है जब इसमें कोई विषम चक्र न हो। प्रेरित उपसमूह के रूप में कोई विषम चक्र या उसका पूरक (ग्राफ़ सिद्धांत) नहीं। द्विभाज्य ग्राफ, द्विभाज्य ग्राफ के रेखा ग्राफ़, और उनके पूरक मजबूत पूर्ण ग्राफ़ प्रमेय के प्रमाण में उपयोग किए जाने वाले पूर्ण ग्राफ़ के पांच बुनियादी वर्गों में से चार बनाते हैं।<ref>{{citation | ||
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | ||
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician) | | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician) | ||
Line 169: | Line 169: | ||
===डिग्री=== | ===डिग्री=== | ||
शीर्ष के लिए, आसन्न शीर्षों की संख्या को शीर्ष की डिग्री (ग्राफ सिद्धांत) कहा जाता है और इसे दर्शाया जाता है <math>\deg(v)</math>. | शीर्ष के लिए, आसन्न शीर्षों की संख्या को शीर्ष की डिग्री (ग्राफ सिद्धांत) कहा जाता है और इसे दर्शाया जाता है <math>\deg(v)</math>. द्विभाज्य ग्राफ के लिए [[डिग्री योग सूत्र]] यह बताता है<ref>{{citation|title=Combinatorial Problems and Exercises|first=László|last=Lovász|author-link=László Lovász|edition=2nd|publisher=Elsevier|year=2014|isbn=9780080933092|page=281|url=https://books.google.com/books?id=wvHiBQAAQBAJ&pg=PA281}}</ref> | ||
:<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math> | :<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math> | ||
द्विभाज्य ग्राफ का डिग्री अनुक्रम सूचियों की जोड़ी है जिसमें प्रत्येक में दो भागों की डिग्री होती है <math>U</math> और <math>V</math>. उदाहरण के लिए, संपूर्ण द्विभाज्य ग्राफ K<sub>3,5</sub> डिग्री अनुक्रम है <math>(5,5,5),(3,3,3,3,3)</math>. आइसोमोर्फिक द्विभाज्य ग्राफ में समान डिग्री अनुक्रम होता है। हालाँकि, डिग्री अनुक्रम, सामान्य तौर पर, विशिष्ट रूप से द्विभाज्य ग्राफ की पहचान नहीं करता है; कुछ मामलों में, गैर-आइसोमोर्फिक द्विभाज्य ग्राफ में समान डिग्री अनुक्रम हो सकता है। | |||
द्विभाज्य बोध समस्या प्राकृतिक संख्याओं की दो दी गई सूचियों के डिग्री अनुक्रम के साथ सरल द्विभाज्य ग्राफ खोजने की समस्या है। (अनुगामी शून्यों को नजरअंदाज किया जा सकता है क्योंकि उन्हें डिग्राफ में उचित संख्या में पृथक शीर्षों को जोड़कर तुच्छ रूप से महसूस किया जाता है।) | |||
===हाइपरग्राफ और निर्देशित ग्राफ से संबंध=== | ===हाइपरग्राफ और निर्देशित ग्राफ से संबंध=== | ||
द्विभाज्य ग्राफ के द्विभाज्य ग्राफ की आसन्नता मैट्रिक्स <math>(U,V,E)</math> आकार का (0,1) मैट्रिक्स है <math>|U|\times|V|</math> इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए और गैर-आसन्न शीर्षों के लिए शून्य है।<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}} शीर्ष आकार का कोई भी (0,1) मैट्रिक्स हो सकता है <math>n\times n</math>, जिसे फिर द्विभाज्य ग्राफ के आसन्न मैट्रिक्स के रूप में पुनः व्याख्या किया जा सकता है {{mvar|n}} इसके द्विभाजन के प्रत्येक तरफ शीर्ष।<ref>{{citation | ||
| last1 = Brualdi | first1 = Richard A. | | last1 = Brualdi | first1 = Richard A. | ||
| last2 = Harary | first2 = Frank | author2-link = Frank Harary | | last2 = Harary | first2 = Frank | author2-link = Frank Harary | ||
Line 200: | Line 200: | ||
| volume = 10 | | volume = 10 | ||
| year = 1958| s2cid = 123363425 | doi-access = free | | year = 1958| s2cid = 123363425 | doi-access = free | ||
}}.</ref> इस निर्माण में, | }}.</ref> इस निर्माण में, द्विभाज्य ग्राफ निर्देशित ग्राफ का [[द्विदलीय दोहरा आवरण|द्विभाज्य दोहरा आवरण]] है। | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
===द्विपक्षीयता का परीक्षण=== | ===द्विपक्षीयता का परीक्षण=== | ||
यह परीक्षण करना संभव है कि क्या कोई ग्राफ | यह परीक्षण करना संभव है कि क्या कोई ग्राफ द्विभाज्य है, और [[गहराई-पहली खोज]] का उपयोग करके, [[रैखिक समय]] में या तो दो-रंग (यदि यह द्विभाज्य है) या विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो गहराई-प्रथम खोज वन में उसके मूल रंग से भिन्न हो, गहराई-प्रथम-खोज वन के [[प्रीऑर्डर ट्रैवर्सल]] में रंग निर्दिष्ट किया जाए। यह आवश्यक रूप से फैले हुए जंगल को दो-रंग प्रदान करेगा जिसमें शीर्षों को उनके माता-पिता से जोड़ने वाले किनारे शामिल होंगे, लेकिन यह कुछ गैर-वन किनारों को ठीक से रंग नहीं सकता है। गहराई-प्रथम खोज वन में, प्रत्येक गैर-वन किनारे के दो समापन बिंदुओं में से दूसरे समापन बिंदु का पूर्वज होता है, और जब गहराई की पहली खोज इस प्रकार के किनारे की खोज करती है तो उसे जांचना चाहिए कि इन दोनों शीर्षों के अलग-अलग रंग हैं। यदि वे ऐसा नहीं करते हैं, तो जंगल में पूर्वज से वंशज तक का पथ, बदरंग किनारे के साथ, विषम चक्र बनाता है, जिसे एल्गोरिदम से इस परिणाम के साथ लौटाया जाता है कि ग्राफ द्विभाज्य नहीं है। हालाँकि, यदि एल्गोरिथ्म इस प्रकार के विषम चक्र का पता लगाए बिना समाप्त हो जाता है, तो प्रत्येक किनारे को उचित रूप से रंगीन होना चाहिए, और एल्गोरिथ्म रंग को इस परिणाम के साथ लौटाता है कि ग्राफ द्विभाज्य है।<ref>{{citation | ||
| last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist) | | last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist) | ||
| edition = 3rd | | edition = 3rd | ||
Line 212: | Line 212: | ||
| title = Algorithms in Java, Part 5: Graph Algorithms | | title = Algorithms in Java, Part 5: Graph Algorithms | ||
| year = 2004}}.</ref> | | year = 2004}}.</ref> | ||
वैकल्पिक रूप से, समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला | वैकल्पिक रूप से, समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला वर्टेक्स मौजूद होता है, तो यह वर्टेक्स चौड़ाई-प्रथम खोज वन में पथों के साथ मिलकर अपने दो अंतिम बिंदुओं को उनके निम्नतम सामान्य पूर्वज से जोड़ता है अजीब चक्र. यदि एल्गोरिथ्म इस तरह से विषम चक्र को खोजे बिना समाप्त हो जाता है, तो उसे उचित रंग मिल गया होगा, और सुरक्षित रूप से यह निष्कर्ष निकाला जा सकता है कि ग्राफ द्विभाज्य है।<ref>{{citation | ||
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg | | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg | ||
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos | | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos | ||
Line 219: | Line 219: | ||
| title = Algorithm Design | | title = Algorithm Design | ||
| year = 2006}}.</ref> | | year = 2006}}.</ref> | ||
के [[प्रतिच्छेदन ग्राफ]]़ के लिए <math>n</math> [[यूक्लिडियन विमान]] में [[रेखा खंड]]ों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ | के [[प्रतिच्छेदन ग्राफ]]़ के लिए <math>n</math> [[यूक्लिडियन विमान]] में [[रेखा खंड]]ों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ द्विभाज्य है और समय में दो-रंग या विषम चक्र लौटाता है <math>O(n\log n)</math>, भले ही ग्राफ स्वयं तक हो सकता है <math>O\left(n^2\right)</math> किनारों.<ref> | ||
{{citation | {{citation | ||
| last = Eppstein | first = David | author-link = David Eppstein | | last = Eppstein | first = David | author-link = David Eppstein | ||
Line 237: | Line 237: | ||
===विषम चक्र अनुप्रस्थ=== | ===विषम चक्र अनुप्रस्थ=== | ||
{{main|Odd cycle transversal}} | {{main|Odd cycle transversal}} | ||
[[File:Odd Cycle Transversal of size 2.png|thumb|आकार 2 के विषम चक्र अनुप्रस्थ वाला ग्राफ: दो नीले निचले शीर्षों को हटाने से | [[File:Odd Cycle Transversal of size 2.png|thumb|आकार 2 के विषम चक्र अनुप्रस्थ वाला ग्राफ: दो नीले निचले शीर्षों को हटाने से द्विभाज्य ग्राफ बनता है।]][[विषम चक्र अनुप्रस्थ]] एनपी-पूर्ण [[ कलन विधि ]] समस्या है जो ग्राफ G = (V,E) और संख्या k दिए जाने पर पूछती है कि क्या k शीर्षों का समुच्चय मौजूद है, जिसे G से हटाने पर परिणामी ग्राफ द्विभाज्य हो जाएगा।<ref name=yannakakis1978node>{{citation | ||
| last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis | | last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis | ||
| contribution = Node-and edge-deletion NP-complete problems | | contribution = Node-and edge-deletion NP-complete problems | ||
Line 258: | Line 258: | ||
| volume = 32 | | volume = 32 | ||
| year = 2004| citeseerx = 10.1.1.112.6357 | | year = 2004| citeseerx = 10.1.1.112.6357 | ||
}}.</ref> विषम चक्र अनुप्रस्थ नाम इस तथ्य से आता है कि ग्राफ | }}.</ref> विषम चक्र अनुप्रस्थ नाम इस तथ्य से आता है कि ग्राफ द्विभाज्य होता है यदि और केवल तभी जब इसमें कोई विषम चक्र (ग्राफ सिद्धांत) न हो। इसलिए, द्विभाज्य ग्राफ प्राप्त करने के लिए ग्राफ से शीर्षों को हटाने के लिए, किसी को सभी विषम चक्रों को हिट करने की आवश्यकता होती है, या तथाकथित विषम चक्र [[ट्रांसवर्सल (कॉम्बिनेटरिक्स)]] समुच्चय ढूंढना होता है। उदाहरण में, ग्राफ़ के प्रत्येक विषम चक्र में नीला (सबसे निचला) शीर्ष होता है, इसलिए उन शीर्षों को हटाने से सभी विषम चक्र समाप्त हो जाते हैं और द्विभाज्य ग्राफ निकल जाता है। | ||
किनारे द्विदलीकरण समस्या ग्राफ को | किनारे द्विदलीकरण समस्या ग्राफ को द्विभाज्य बनाने के लिए जितना संभव हो उतना कम किनारों को हटाने की एल्गोरिथम समस्या है और यह ग्राफ संशोधन एल्गोरिदम में भी महत्वपूर्ण समस्या है। यह समस्या भी निश्चित-पैरामीटर सुव्यवस्थित है, और इसे समय पर हल किया जा सकता है <math display="inline">O\left(2^k m^2\right)</math>,<ref name=guo2006compression>{{citation | ||
| last1 = Guo | first1 = Jiong | | last1 = Guo | first1 = Jiong | ||
| last2 = Gramm | first2 = Jens | | last2 = Gramm | first2 = Jens | ||
Line 286: | Line 286: | ||
| publisher = Prentice Hall | | publisher = Prentice Hall | ||
| title = Network Flows: Theory, Algorithms, and Applications | | title = Network Flows: Theory, Algorithms, and Applications | ||
| year = 1993}}.</ref> कई मामलों में, गैर-द्विपक्षीय ग्राफ़ की तुलना में मिलान समस्याओं को | | year = 1993}}.</ref> कई मामलों में, गैर-द्विपक्षीय ग्राफ़ की तुलना में मिलान समस्याओं को द्विभाज्य ग्राफ पर हल करना आसान होता है,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> और अधिकतम कार्डिनैलिटी मिलान के लिए हॉपक्रॉफ्ट-कार्प एल्गोरिदम जैसे कई मिलान एल्गोरिदम<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> केवल द्विभाज्य इनपुट पर सही ढंग से काम करें। | ||
सरल उदाहरण के रूप में, मान लीजिए कि | सरल उदाहरण के रूप में, मान लीजिए कि समुच्चय <math>P</math> सभी लोग समूह के बीच से नौकरी की तलाश कर रहे हैं <math>J</math> नौकरियों की, सभी लोग सभी नौकरियों के लिए उपयुक्त नहीं हैं। इस स्थिति को द्विभाज्य ग्राफ के रूप में प्रतिरूपित किया जा सकता है <math>(P,J,E)</math> जहां वर्टेक्स प्रत्येक नौकरी चाहने वाले को प्रत्येक उपयुक्त नौकरी से जोड़ता है।<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> आदर्श मिलान सभी नौकरी चाहने वालों को साथ संतुष्ट करने और सभी नौकरियों को भरने का तरीका बताता है; हॉल का विवाह प्रमेय द्विभाज्य ग्राफ का लक्षण वर्णन प्रदान करता है जो पूर्ण मिलान की अनुमति देता है। [[राष्ट्रीय निवासी मिलान कार्यक्रम]] संयुक्त राज्य अमेरिका में चिकित्सा शिक्षा के लिए इस समस्या को हल करने के लिए ग्राफ़ मिलान विधियों को लागू करता है। मेडिकल छात्र नौकरी चाहने वाले और [[रेजीडेंसी (चिकित्सा)]] नौकरियां।<ref>{{citation | ||
|last = Robinson | |last = Robinson | ||
|first = Sara | |first = Sara | ||
Line 302: | Line 302: | ||
|url-status = dead | |url-status = dead | ||
}}.</ref> | }}.</ref> | ||
डलमेज-मेंडेलसोहन अपघटन | डलमेज-मेंडेलसोहन अपघटन द्विभाज्य ग्राफ का संरचनात्मक अपघटन है जो अधिकतम मिलान खोजने में उपयोगी है।<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref> | ||
==अतिरिक्त अनुप्रयोग== | ==अतिरिक्त अनुप्रयोग== | ||
आधुनिक [[कोडिंग सिद्धांत]] में | आधुनिक [[कोडिंग सिद्धांत]] में द्विभाज्य ग्राफ का व्यापक रूप से उपयोग किया जाता है, विशेष रूप से चैनल से प्राप्त [[कोडवर्ड]] को डिकोड करने के लिए। [[कारक ग्राफ]] और टैनर ग्राफ़ इसके उदाहरण हैं। [[टान्नर ग्राफ]] द्विभाज्य ग्राफ है जिसमें द्विविभाजन के तरफ के कोने कोडवर्ड के अंकों का प्रतिनिधित्व करते हैं, और दूसरी तरफ के कोने उन अंकों के संयोजन का प्रतिनिधित्व करते हैं जिनका कोडवर्ड में त्रुटियों के बिना शून्य होने की उम्मीद है।<ref>{{citation | ||
| last = Moon | first = Todd K. | | last = Moon | first = Todd K. | ||
| isbn = 9780471648000 | | isbn = 9780471648000 | ||
Line 314: | Line 314: | ||
| url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638 | | url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638 | ||
| year = 2005}}.</ref> फ़ैक्टर ग्राफ़ निकट से संबंधित [[विश्वास नेटवर्क]] है जिसका उपयोग [[एलडीपीसी]] और [[टर्बो कोड]] के संभाव्य डिकोडिंग के लिए किया जाता है।<ref>{{harvtxt|Moon|2005}}, p. 686.</ref> | | year = 2005}}.</ref> फ़ैक्टर ग्राफ़ निकट से संबंधित [[विश्वास नेटवर्क]] है जिसका उपयोग [[एलडीपीसी]] और [[टर्बो कोड]] के संभाव्य डिकोडिंग के लिए किया जाता है।<ref>{{harvtxt|Moon|2005}}, p. 686.</ref> | ||
कंप्यूटर विज्ञान में, [[पेट्री नेट]] गणितीय मॉडलिंग उपकरण है जिसका उपयोग समवर्ती प्रणालियों के विश्लेषण और सिमुलेशन में किया जाता है। सिस्टम को नोड्स के दो सेटों के साथ | कंप्यूटर विज्ञान में, [[पेट्री नेट]] गणितीय मॉडलिंग उपकरण है जिसका उपयोग समवर्ती प्रणालियों के विश्लेषण और सिमुलेशन में किया जाता है। सिस्टम को नोड्स के दो सेटों के साथ द्विभाज्य निर्देशित ग्राफ के रूप में तैयार किया जाता है: स्थान नोड्स का समुच्चय जिसमें संसाधन होते हैं, और इवेंट नोड्स का समुच्चय जो संसाधनों को उत्पन्न और/या उपभोग करता है। नोड्स और किनारों पर अतिरिक्त बाधाएं हैं जो सिस्टम के व्यवहार को बाधित करती हैं। पेट्री नेट सिस्टम के व्यवहार के गणितीय प्रमाण की अनुमति देने के लिए द्विभाज्य निर्देशित ग्राफ़ और अन्य गुणों का उपयोग करते हैं, साथ ही सिस्टम के सिमुलेशन के आसान कार्यान्वयन की अनुमति भी देते हैं।<ref>{{citation | ||
| last1 = Cassandras | first1 = Christos G. | | last1 = Cassandras | first1 = Christos G. | ||
| last2 = Lafortune | first2 = Stephane | | last2 = Lafortune | first2 = Stephane | ||
Line 324: | Line 324: | ||
| url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224 | | url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224 | ||
| year = 2007}}.</ref> | | year = 2007}}.</ref> | ||
[[प्रक्षेप्य ज्यामिति]] में, [[लेवी ग्राफ]]़ | [[प्रक्षेप्य ज्यामिति]] में, [[लेवी ग्राफ]]़ द्विभाज्य ग्राफ का रूप है जिसका उपयोग किसी कॉन्फ़िगरेशन (ज्यामिति) में बिंदुओं और रेखाओं के बीच की घटनाओं को मॉडल करने के लिए किया जाता है। बिंदुओं और रेखाओं की ज्यामितीय संपत्ति के अनुरूप, प्रत्येक दो रेखाएं अधिकतम बिंदु पर मिलती हैं और प्रत्येक दो बिंदु ही रेखा से जुड़े होते हैं, लेवी ग्राफ़ में आवश्यक रूप से लंबाई चार का कोई चक्र नहीं होता है, इसलिए उनकी [[परिधि (ग्राफ़ सिद्धांत)]] अवश्य होनी चाहिए छह या अधिक हों.<ref>{{citation | ||
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum | | last = Grünbaum | first = Branko | author-link = Branko Grünbaum | ||
| isbn = 9780821843086 | | isbn = 9780821843086 | ||
Line 337: | Line 337: | ||
==यह भी देखें== | ==यह भी देखें== | ||
*द्विपक्षीय आयाम, पूर्ण | *द्विपक्षीय आयाम, पूर्ण द्विभाज्य ग्राफ की न्यूनतम संख्या जिसका संघ दिया गया ग्राफ़ है | ||
*द्विपक्षीय दोहरा आवरण, किसी भी ग्राफ़ को उसके शीर्षों को दोगुना करके | *द्विपक्षीय दोहरा आवरण, किसी भी ग्राफ़ को उसके शीर्षों को दोगुना करके द्विभाज्य ग्राफ में बदलने का तरीका | ||
*द्विपक्षीय हाइपरग्राफ, हाइपरग्राफ के लिए द्विदलीयता का सामान्यीकरण। | *द्विपक्षीय हाइपरग्राफ, हाइपरग्राफ के लिए द्विदलीयता का सामान्यीकरण। | ||
*द्विपक्षीय मैट्रोइड, मैट्रोइड्स का वर्ग जिसमें | *द्विपक्षीय मैट्रोइड, मैट्रोइड्स का वर्ग जिसमें द्विभाज्य ग्राफ के [[ग्राफ़िक मैट्रोइड]] शामिल हैं | ||
*द्विपक्षीय नेटवर्क प्रक्षेपण, | *द्विपक्षीय नेटवर्क प्रक्षेपण, द्विभाज्य नेटवर्क के बारे में जानकारी को संपीड़ित करने के लिए भार तकनीक | ||
*[[उत्तल द्विदलीय ग्राफ]], | *[[उत्तल द्विदलीय ग्राफ|उत्तल द्विभाज्य ग्राफ]], द्विभाज्य ग्राफ जिसके शीर्षों को क्रमबद्ध किया जा सकता है ताकि शीर्ष पड़ोस सन्निहित हों | ||
*[[बहुपक्षीय ग्राफ]]़, शीर्षों के दो से अधिक उपसमूहों के लिए | *[[बहुपक्षीय ग्राफ]]़, शीर्षों के दो से अधिक उपसमूहों के लिए द्विभाज्य ग्राफ का सामान्यीकरण | ||
*[[समता ग्राफ]]़, | *[[समता ग्राफ]]़, द्विभाज्य ग्राफ का सामान्यीकरण जिसमें समान दो बिंदुओं के बीच प्रत्येक दो [[प्रेरित पथ]]ों में समान समता होती है | ||
*[[अर्ध-द्विपक्षीय ग्राफ]]़, प्रकार का स्टीनर ट्री समस्या उदाहरण जिसमें टर्मिनल स्वतंत्र | *[[अर्ध-द्विपक्षीय ग्राफ]]़, प्रकार का स्टीनर ट्री समस्या उदाहरण जिसमें टर्मिनल स्वतंत्र समुच्चय बनाते हैं, जो सन्निकटन एल्गोरिदम की अनुमति देता है जो द्विभाज्य ग्राफ के लिए सामान्यीकरण करता है | ||
*[[ विभाजित ग्राफ ]]़, ग्राफ़ जिसमें शीर्षों को दो उपसमूहों में विभाजित किया जा सकता है, जिनमें से स्वतंत्र है और दूसरा समूह है | *[[ विभाजित ग्राफ ]]़, ग्राफ़ जिसमें शीर्षों को दो उपसमूहों में विभाजित किया जा सकता है, जिनमें से स्वतंत्र है और दूसरा समूह है | ||
*निषिद्ध उपसमूहों वाले | *निषिद्ध उपसमूहों वाले द्विभाज्य ग्राफ में किनारों की अधिकतम संख्या पर [[ज़ारांकिविज़ समस्या]] | ||
==संदर्भ== | ==संदर्भ== |
Revision as of 09:19, 23 July 2023
ग्राफ सिद्धांत के गणित क्षेत्र में, द्विभाज्य ग्राफ (या बिग्राफ) एक ऐसा ग्राफ (असतत गणित) है जिसके शीर्षों (ग्राफ सिद्धांत) को दो असंयुक्त समुच्चय और स्वतंत्र समुच्चय (ग्राफ सिद्धांत) और में विभाजित किया जा सकता है। अर्थात्, प्रत्येक वर्टेक्स (ग्राफ़ सिद्धांत) में एक शीर्ष को में एक से जोड़ता है। वर्टेक्स समुच्चय और को सामान्यतः ग्राफ़ के भाग कहा जाता है। समान रूप से, एक द्विभाज्य ग्राफ ऐसा ग्राफ है जिसमें कोई विषम-लंबाई चक्र (ग्राफ सिद्धांत) नहीं होता है।[1][2]
दो समुच्चय और इसे ग्राफ़ को दो रंगों से रंगने के रूप में सोचा जा सकता है: यदि कोई सभी नोड्स को नीले रंग में रंगता है, और सभी नोड्स को लाल रंग में रंगता है, तो प्रत्येक किनारे पर अलग-अलग रंगों के समापन बिंदु होते हैं, जैसा कि ग्राफ़ रंग समस्या में आवश्यक है।[3][4] इसके विपरीत, गैर-द्विपक्षीय ग्राफ़ के स्थिति में ऐसा रंग असंभव है, जैसे कि त्रिकोण: एक नोड को नीला और दूसरे को लाल रंग देने के बाद, त्रिकोण का तीसरा शीर्ष दोनों रंगों के शीर्षों से जुड़ा होता है, जिससे इसे किसी भी रंग को निर्दिष्ट करने से रोका जा सकता है।
एक द्विभाज्य ग्राफ़ को दर्शाने के लिए अधिकांश लिखा जाता है जिसके विभाजन में और भाग होते हैं, ग्राफ़ के किनारों को दर्शाता है। यदि एक द्विभाज्य ग्राफ जुड़ा हुआ ग्राफ़ नहीं है, तो इसमें से अधिक द्विविभाजन हो सकते हैं;[5] इस स्थिति में, नोटेशन एक विशेष द्विविभाजन को निर्दिष्ट करने में सहायक होता है जो किसी अनुप्रयोग में महत्वपूर्ण हो सकता है। यदि , अर्थात, यदि दो उपसमुच्चयों में समान कार्डिनैलिटी है, तो को संतुलित द्विभाज्य ग्राफ कहा जाता है।[3] यदि द्विविभाजन के एक ही तरफ के सभी शीर्षों की डिग्री (ग्राफ सिद्धांत) समान है, तो द्विविभाजन ग्राफ कहलाता है।
उदाहरण
वस्तुओं के दो अलग-अलग वर्गों के बीच विषम संबंध मॉडलिंग करते समय, द्विभाज्य ग्राफ अधिकांश स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए, फुटबॉल खिलाड़ियों और क्लबों का ग्राफ, खिलाड़ी और क्लब के बीच बढ़त के साथ, यदि खिलाड़ी उस क्लब के लिए खेला है, संबद्धता नेटवर्क का प्राकृतिक उदाहरण है, जो सामाजिक नेटवर्क विश्लेषण में उपयोग किया जाने वाला प्रकार का द्विभाज्य ग्राफ है।[6] अन्य उदाहरण जहां द्विभाज्य ग्राफ स्वाभाविक रूप से दिखाई देते हैं वह (एनपी-पूर्ण) रेलवे अनुकूलन समस्या है, जिसमें इनपुट ट्रेनों और उनके स्टॉप का शेड्यूल है, और लक्ष्य ट्रेन स्टेशनों का समुच्चय जितना संभव हो उतना छोटा ढूंढना है ताकि प्रत्येक ट्रेन चुने गए स्टेशनों में से कम से कम पर जाती है। इस समस्या को द्विभाज्य ग्राफ में प्रमुख समुच्चय समस्या के रूप में तैयार किया जा सकता है जिसमें प्रत्येक ट्रेन और प्रत्येक स्टेशन के लिए शीर्ष होता है और स्टेशन और उस स्टेशन पर रुकने वाली ट्रेन के प्रत्येक जोड़े के लिए वर्टेक्स होता है।[7] तीसरा उदाहरण मुद्राशास्त्र के शैक्षणिक क्षेत्र में है। प्राचीन सिक्के डिज़ाइन के दो सकारात्मक प्रभावों (सामने और पीछे) का उपयोग करके बनाए जाते हैं। मुद्राशास्त्री सिक्कों के उत्पादन को दर्शाने के लिए जो चार्ट बनाते हैं, वे द्विभाज्य ग्राफ होते हैं।[8] अधिक सारगर्भित उदाहरणों में निम्नलिखित शामिल हैं:
- प्रत्येक वृक्ष (ग्राफ़ सिद्धांत) द्विभाज्य है।[4]* सम संख्या में शीर्षों वाले चक्र ग्राफ ़ द्विभाज्य होते हैं।[4]* प्रत्येक समतलीय ग्राफ, जिसकी ग्राफ सिद्धांत #जीनस की शब्दावली में सभी की लंबाई सम है, द्विभाज्य है।[9] इसके विशेष स्थिति ग्रिड ग्राफ़ और वर्गाकार हैं, जिनमें प्रत्येक आंतरिक फलक में 4 किनारे होते हैं और प्रत्येक आंतरिक शीर्ष पर चार या अधिक पड़ोसी होते हैं।[10]
- एम और एन शीर्षों पर पूर्ण द्विभाज्य ग्राफ, के द्वारा निरूपितn,mद्विदलीय ग्राफ है , जहां U और V क्रमशः m और n आकार के असंयुक्त समुच्चय हैं, और E, U के प्रत्येक शीर्ष को V के सभी शीर्षों से जोड़ता है। यह इस प्रकार है कि Km,nएमएन किनारे हैं।[11] पूर्ण द्विभाज्य ग्राफ से निकटता से संबंधित ताज ग्राफ ़ हैं, जो पूर्ण मिलान के किनारों को हटाकर पूर्ण द्विभाज्य ग्राफ से बनते हैं।[12]
- हाइपरक्यूब ग्राफ़, आंशिक क्यूब्स और माध्यिका ग्राफ़ द्विभाज्य हैं। इन ग्राफ़ों में, शीर्षों को बिटवेक्टरों द्वारा इस तरह से लेबल किया जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल यदि संबंधित बिटवेक्टर ही स्थिति में भिन्न हों। उन शीर्षों को अलग करके द्विविभाजन बनाया जा सकता है जिनके बिटवेक्टर में विषम संख्या वाले शीर्षों से इकाइयों की संख्या सम है। पेड़ और वर्गालेख माध्यिका ग्राफ़ के उदाहरण बनाते हैं, और प्रत्येक माध्यिका ग्राफ़ आंशिक घन है।[13]
गुण
लक्षणीकरण
द्विभाज्य ग्राफ को कई अलग-अलग तरीकों से चित्रित किया जा सकता है:
- अप्रत्यक्ष ग्राफ़ द्विभाज्य है यदि और केवल तभी जब इसमें कोई चक्र (ग्राफ़ सिद्धांत) शामिल न हो।[14][15]
- ग्राफ़ द्विभाज्य है यदि और केवल यदि वह 2-रंगीय है, (अर्थात इसकी वर्णिक संख्या 2 से कम या उसके बराबर है)।[3]* ग्राफ द्विभाज्य होता है यदि और केवल यदि प्रत्येक वर्टेक्स विषम संख्या में कट (ग्राफ सिद्धांत) से संबंधित हो, किनारों के न्यूनतम उपसमूह जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।[16] * ग्राफ़ द्विभाज्य है यदि और केवल यदि ग्राफ़ का वर्णक्रमीय ग्राफ़ सिद्धांत सममित है।[17]
कोनिग का प्रमेय और पूर्ण ग्राफ
द्विभाज्य ग्राफ में, न्यूनतम शीर्ष कवर का आकार अधिकतम मिलान के आकार के बराबर होता है; यह कोनिग का प्रमेय (ग्राफ सिद्धांत) है|कोनिग का प्रमेय।[18][19] इस प्रमेय का वैकल्पिक और समतुल्य रूप यह है कि अधिकतम स्वतंत्र समुच्चय का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर है। पृथक शीर्ष के बिना किसी भी ग्राफ़ में न्यूनतम किनारे कवर का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के बराबर होता है।[20] इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, द्विभाज्य ग्राफ में, न्यूनतम किनारे कवर का आकार अधिकतम स्वतंत्र समुच्चय के आकार के बराबर होता है, और न्यूनतम किनारे कवर का आकार और न्यूनतम शीर्ष कवर का आकार होता है शीर्षों की संख्या के बराबर है.
संबंधित परिणामों का अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विभाज्य ग्राफ, प्रत्येक द्विभाज्य ग्राफ का पूरक (ग्राफ सिद्धांत), प्रत्येक द्विभाज्य ग्राफ का रेखा ग्राफ़, और प्रत्येक द्विभाज्य ग्राफ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विभाज्य ग्राफ की पूर्णता देखना आसान है (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) लेकिन द्विभाज्य ग्राफ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का और पुनर्कथन है। यह उन परिणामों में से था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया।[21] पूर्ण ग्राफ़ के लाइन ग्राफ़ के पूरकों की पूर्णता कोनिग के प्रमेय का और पुनर्कथन है, और लाइन ग्राफ़ की पूर्णता स्वयं कोनिग के पहले के प्रमेय का पुनर्कथन है, कि प्रत्येक द्विभाज्य ग्राफ में कई रंगों का उपयोग करके किनारे का रंग होता है इसकी अधिकतम डिग्री.
मजबूत परफेक्ट ग्राफ प्रमेय के अनुसार, परफेक्ट ग्राफ में द्विभाज्य ग्राफ के समान निषिद्ध ग्राफ लक्षण वर्णन होता है: ग्राफ द्विभाज्य होता है यदि और केवल तभी जब इसमें सबग्राफ के रूप में कोई विषम चक्र न हो, और ग्राफ तभी सही होता है जब इसमें कोई विषम चक्र न हो। प्रेरित उपसमूह के रूप में कोई विषम चक्र या उसका पूरक (ग्राफ़ सिद्धांत) नहीं। द्विभाज्य ग्राफ, द्विभाज्य ग्राफ के रेखा ग्राफ़, और उनके पूरक मजबूत पूर्ण ग्राफ़ प्रमेय के प्रमाण में उपयोग किए जाने वाले पूर्ण ग्राफ़ के पांच बुनियादी वर्गों में से चार बनाते हैं।[22]
डिग्री
शीर्ष के लिए, आसन्न शीर्षों की संख्या को शीर्ष की डिग्री (ग्राफ सिद्धांत) कहा जाता है और इसे दर्शाया जाता है . द्विभाज्य ग्राफ के लिए डिग्री योग सूत्र यह बताता है[23]
द्विभाज्य ग्राफ का डिग्री अनुक्रम सूचियों की जोड़ी है जिसमें प्रत्येक में दो भागों की डिग्री होती है और . उदाहरण के लिए, संपूर्ण द्विभाज्य ग्राफ K3,5 डिग्री अनुक्रम है . आइसोमोर्फिक द्विभाज्य ग्राफ में समान डिग्री अनुक्रम होता है। हालाँकि, डिग्री अनुक्रम, सामान्य तौर पर, विशिष्ट रूप से द्विभाज्य ग्राफ की पहचान नहीं करता है; कुछ मामलों में, गैर-आइसोमोर्फिक द्विभाज्य ग्राफ में समान डिग्री अनुक्रम हो सकता है।
द्विभाज्य बोध समस्या प्राकृतिक संख्याओं की दो दी गई सूचियों के डिग्री अनुक्रम के साथ सरल द्विभाज्य ग्राफ खोजने की समस्या है। (अनुगामी शून्यों को नजरअंदाज किया जा सकता है क्योंकि उन्हें डिग्राफ में उचित संख्या में पृथक शीर्षों को जोड़कर तुच्छ रूप से महसूस किया जाता है।)
हाइपरग्राफ और निर्देशित ग्राफ से संबंध
द्विभाज्य ग्राफ के द्विभाज्य ग्राफ की आसन्नता मैट्रिक्स आकार का (0,1) मैट्रिक्स है इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए और गैर-आसन्न शीर्षों के लिए शून्य है।[24] द्विभाज्य ग्राफ, हाइपरग्राफ़ और निर्देशित ग्राफ़ के बीच समानता का वर्णन करने के लिए द्विआसन्नता मैट्रिक्स का उपयोग किया जा सकता है।
हाइपरग्राफ संयोजी संरचना है, जिसमें अप्रत्यक्ष ग्राफ की तरह, शीर्ष और किनारे होते हैं, लेकिन जिसमें किनारों में बिल्कुल दो समापन बिंदु होने के अतिरिक्त शीर्षों का मनमाना समुच्चय हो सकता है। द्विभाज्य ग्राफ जिसमें हाइपरग्राफ को मॉडल करने के लिए उपयोग किया जा सकता है U हाइपरग्राफ के शीर्षों का समुच्चय है, V हाइपरएज का समुच्चय है, और E में हाइपरग्राफ शीर्ष से वर्टेक्स होता है v हाइपरग्राफ किनारे तक e बिलकुल कब v के अंतिम बिंदुओं में से है e. इस पत्राचार के तहत, द्विभाज्य ग्राफ के द्विआसन्नता मैट्रिक्स वास्तव में संबंधित हाइपरग्राफ के घटना मैट्रिक्स हैं। द्विभाज्य ग्राफ और हाइपरग्राफ के बीच इस पत्राचार के विशेष स्थिति के रूप में, किसी भी मल्टीग्राफ (ग्राफ जिसमें समान दो शीर्षों के बीच दो या दो से अधिक किनारे हो सकते हैं) को हाइपरग्राफ के रूप में व्याख्या किया जा सकता है जिसमें कुछ हाइपरएज में समापन बिंदुओं के समान समुच्चय होते हैं, और द्विभाज्य ग्राफ द्वारा दर्शाया गया है जिसमें एकाधिक आसन्नताएं नहीं हैं और जिसमें द्विविभाजन के तरफ के सभी शीर्षों की डिग्री (ग्राफ सिद्धांत) दो है।[25] निकटवर्ती मैट्रिक्स की समान पुनर्व्याख्या का उपयोग निर्देशित ग्राफ़ (लेबल वाले शीर्षों की दी गई संख्या पर, स्व-लूप की अनुमति) और संतुलित द्विभाज्य ग्राफ के बीच एक-से-पत्राचार दिखाने के लिए किया जा सकता है, जिसमें दोनों तरफ समान संख्या में कोने होते हैं। द्विविभाजन. के लिए, निर्देशित ग्राफ के आसन्न मैट्रिक्स के साथ n शीर्ष आकार का कोई भी (0,1) मैट्रिक्स हो सकता है , जिसे फिर द्विभाज्य ग्राफ के आसन्न मैट्रिक्स के रूप में पुनः व्याख्या किया जा सकता है n इसके द्विभाजन के प्रत्येक तरफ शीर्ष।[26] इस निर्माण में, द्विभाज्य ग्राफ निर्देशित ग्राफ का द्विभाज्य दोहरा आवरण है।
एल्गोरिदम
द्विपक्षीयता का परीक्षण
यह परीक्षण करना संभव है कि क्या कोई ग्राफ द्विभाज्य है, और गहराई-पहली खोज का उपयोग करके, रैखिक समय में या तो दो-रंग (यदि यह द्विभाज्य है) या विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो गहराई-प्रथम खोज वन में उसके मूल रंग से भिन्न हो, गहराई-प्रथम-खोज वन के प्रीऑर्डर ट्रैवर्सल में रंग निर्दिष्ट किया जाए। यह आवश्यक रूप से फैले हुए जंगल को दो-रंग प्रदान करेगा जिसमें शीर्षों को उनके माता-पिता से जोड़ने वाले किनारे शामिल होंगे, लेकिन यह कुछ गैर-वन किनारों को ठीक से रंग नहीं सकता है। गहराई-प्रथम खोज वन में, प्रत्येक गैर-वन किनारे के दो समापन बिंदुओं में से दूसरे समापन बिंदु का पूर्वज होता है, और जब गहराई की पहली खोज इस प्रकार के किनारे की खोज करती है तो उसे जांचना चाहिए कि इन दोनों शीर्षों के अलग-अलग रंग हैं। यदि वे ऐसा नहीं करते हैं, तो जंगल में पूर्वज से वंशज तक का पथ, बदरंग किनारे के साथ, विषम चक्र बनाता है, जिसे एल्गोरिदम से इस परिणाम के साथ लौटाया जाता है कि ग्राफ द्विभाज्य नहीं है। हालाँकि, यदि एल्गोरिथ्म इस प्रकार के विषम चक्र का पता लगाए बिना समाप्त हो जाता है, तो प्रत्येक किनारे को उचित रूप से रंगीन होना चाहिए, और एल्गोरिथ्म रंग को इस परिणाम के साथ लौटाता है कि ग्राफ द्विभाज्य है।[27] वैकल्पिक रूप से, समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला वर्टेक्स मौजूद होता है, तो यह वर्टेक्स चौड़ाई-प्रथम खोज वन में पथों के साथ मिलकर अपने दो अंतिम बिंदुओं को उनके निम्नतम सामान्य पूर्वज से जोड़ता है अजीब चक्र. यदि एल्गोरिथ्म इस तरह से विषम चक्र को खोजे बिना समाप्त हो जाता है, तो उसे उचित रंग मिल गया होगा, और सुरक्षित रूप से यह निष्कर्ष निकाला जा सकता है कि ग्राफ द्विभाज्य है।[28] के प्रतिच्छेदन ग्राफ़ के लिए यूक्लिडियन विमान में रेखा खंडों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ द्विभाज्य है और समय में दो-रंग या विषम चक्र लौटाता है , भले ही ग्राफ स्वयं तक हो सकता है किनारों.[29]
विषम चक्र अनुप्रस्थ
विषम चक्र अनुप्रस्थ एनपी-पूर्ण कलन विधि समस्या है जो ग्राफ G = (V,E) और संख्या k दिए जाने पर पूछती है कि क्या k शीर्षों का समुच्चय मौजूद है, जिसे G से हटाने पर परिणामी ग्राफ द्विभाज्य हो जाएगा।[30] समस्या पैरामीटरीकृत जटिलता | निश्चित-पैरामीटर ट्रैक्टेबल है, जिसका अर्थ है कि एल्गोरिदम है जिसका चलने का समय ग्राफ के आकार के बहुपद फ़ंक्शन द्वारा k के बड़े फ़ंक्शन से गुणा किया जा सकता है।[31] विषम चक्र अनुप्रस्थ नाम इस तथ्य से आता है कि ग्राफ द्विभाज्य होता है यदि और केवल तभी जब इसमें कोई विषम चक्र (ग्राफ सिद्धांत) न हो। इसलिए, द्विभाज्य ग्राफ प्राप्त करने के लिए ग्राफ से शीर्षों को हटाने के लिए, किसी को सभी विषम चक्रों को हिट करने की आवश्यकता होती है, या तथाकथित विषम चक्र ट्रांसवर्सल (कॉम्बिनेटरिक्स) समुच्चय ढूंढना होता है। उदाहरण में, ग्राफ़ के प्रत्येक विषम चक्र में नीला (सबसे निचला) शीर्ष होता है, इसलिए उन शीर्षों को हटाने से सभी विषम चक्र समाप्त हो जाते हैं और द्विभाज्य ग्राफ निकल जाता है।
किनारे द्विदलीकरण समस्या ग्राफ को द्विभाज्य बनाने के लिए जितना संभव हो उतना कम किनारों को हटाने की एल्गोरिथम समस्या है और यह ग्राफ संशोधन एल्गोरिदम में भी महत्वपूर्ण समस्या है। यह समस्या भी निश्चित-पैरामीटर सुव्यवस्थित है, और इसे समय पर हल किया जा सकता है ,[32] जहां k हटाए जाने वाले किनारों की संख्या है और m इनपुट ग्राफ़ में किनारों की संख्या है।
मिलान
ग्राफ़ में मिलान (ग्राफ़ सिद्धांत) उसके किनारों का उपसमुच्चय है, जिनमें से कोई भी दो समापन बिंदु साझा नहीं करते हैं। बहुपद समय एल्गोरिदम मिलान पर कई एल्गोरिथम समस्याओं के लिए जाना जाता है, जिसमें अधिकतम मिलान (मिलान ढूंढना जो जितना संभव हो उतने किनारों का उपयोग करता है), अधिकतम वजन मिलान और स्थिर विवाह शामिल है।[33] कई मामलों में, गैर-द्विपक्षीय ग्राफ़ की तुलना में मिलान समस्याओं को द्विभाज्य ग्राफ पर हल करना आसान होता है,[34] और अधिकतम कार्डिनैलिटी मिलान के लिए हॉपक्रॉफ्ट-कार्प एल्गोरिदम जैसे कई मिलान एल्गोरिदम[35] केवल द्विभाज्य इनपुट पर सही ढंग से काम करें।
सरल उदाहरण के रूप में, मान लीजिए कि समुच्चय सभी लोग समूह के बीच से नौकरी की तलाश कर रहे हैं नौकरियों की, सभी लोग सभी नौकरियों के लिए उपयुक्त नहीं हैं। इस स्थिति को द्विभाज्य ग्राफ के रूप में प्रतिरूपित किया जा सकता है जहां वर्टेक्स प्रत्येक नौकरी चाहने वाले को प्रत्येक उपयुक्त नौकरी से जोड़ता है।[36] आदर्श मिलान सभी नौकरी चाहने वालों को साथ संतुष्ट करने और सभी नौकरियों को भरने का तरीका बताता है; हॉल का विवाह प्रमेय द्विभाज्य ग्राफ का लक्षण वर्णन प्रदान करता है जो पूर्ण मिलान की अनुमति देता है। राष्ट्रीय निवासी मिलान कार्यक्रम संयुक्त राज्य अमेरिका में चिकित्सा शिक्षा के लिए इस समस्या को हल करने के लिए ग्राफ़ मिलान विधियों को लागू करता है। मेडिकल छात्र नौकरी चाहने वाले और रेजीडेंसी (चिकित्सा) नौकरियां।[37] डलमेज-मेंडेलसोहन अपघटन द्विभाज्य ग्राफ का संरचनात्मक अपघटन है जो अधिकतम मिलान खोजने में उपयोगी है।[38]
अतिरिक्त अनुप्रयोग
आधुनिक कोडिंग सिद्धांत में द्विभाज्य ग्राफ का व्यापक रूप से उपयोग किया जाता है, विशेष रूप से चैनल से प्राप्त कोडवर्ड को डिकोड करने के लिए। कारक ग्राफ और टैनर ग्राफ़ इसके उदाहरण हैं। टान्नर ग्राफ द्विभाज्य ग्राफ है जिसमें द्विविभाजन के तरफ के कोने कोडवर्ड के अंकों का प्रतिनिधित्व करते हैं, और दूसरी तरफ के कोने उन अंकों के संयोजन का प्रतिनिधित्व करते हैं जिनका कोडवर्ड में त्रुटियों के बिना शून्य होने की उम्मीद है।[39] फ़ैक्टर ग्राफ़ निकट से संबंधित विश्वास नेटवर्क है जिसका उपयोग एलडीपीसी और टर्बो कोड के संभाव्य डिकोडिंग के लिए किया जाता है।[40] कंप्यूटर विज्ञान में, पेट्री नेट गणितीय मॉडलिंग उपकरण है जिसका उपयोग समवर्ती प्रणालियों के विश्लेषण और सिमुलेशन में किया जाता है। सिस्टम को नोड्स के दो सेटों के साथ द्विभाज्य निर्देशित ग्राफ के रूप में तैयार किया जाता है: स्थान नोड्स का समुच्चय जिसमें संसाधन होते हैं, और इवेंट नोड्स का समुच्चय जो संसाधनों को उत्पन्न और/या उपभोग करता है। नोड्स और किनारों पर अतिरिक्त बाधाएं हैं जो सिस्टम के व्यवहार को बाधित करती हैं। पेट्री नेट सिस्टम के व्यवहार के गणितीय प्रमाण की अनुमति देने के लिए द्विभाज्य निर्देशित ग्राफ़ और अन्य गुणों का उपयोग करते हैं, साथ ही सिस्टम के सिमुलेशन के आसान कार्यान्वयन की अनुमति भी देते हैं।[41] प्रक्षेप्य ज्यामिति में, लेवी ग्राफ़ द्विभाज्य ग्राफ का रूप है जिसका उपयोग किसी कॉन्फ़िगरेशन (ज्यामिति) में बिंदुओं और रेखाओं के बीच की घटनाओं को मॉडल करने के लिए किया जाता है। बिंदुओं और रेखाओं की ज्यामितीय संपत्ति के अनुरूप, प्रत्येक दो रेखाएं अधिकतम बिंदु पर मिलती हैं और प्रत्येक दो बिंदु ही रेखा से जुड़े होते हैं, लेवी ग्राफ़ में आवश्यक रूप से लंबाई चार का कोई चक्र नहीं होता है, इसलिए उनकी परिधि (ग्राफ़ सिद्धांत) अवश्य होनी चाहिए छह या अधिक हों.[42]
यह भी देखें
- द्विपक्षीय आयाम, पूर्ण द्विभाज्य ग्राफ की न्यूनतम संख्या जिसका संघ दिया गया ग्राफ़ है
- द्विपक्षीय दोहरा आवरण, किसी भी ग्राफ़ को उसके शीर्षों को दोगुना करके द्विभाज्य ग्राफ में बदलने का तरीका
- द्विपक्षीय हाइपरग्राफ, हाइपरग्राफ के लिए द्विदलीयता का सामान्यीकरण।
- द्विपक्षीय मैट्रोइड, मैट्रोइड्स का वर्ग जिसमें द्विभाज्य ग्राफ के ग्राफ़िक मैट्रोइड शामिल हैं
- द्विपक्षीय नेटवर्क प्रक्षेपण, द्विभाज्य नेटवर्क के बारे में जानकारी को संपीड़ित करने के लिए भार तकनीक
- उत्तल द्विभाज्य ग्राफ, द्विभाज्य ग्राफ जिसके शीर्षों को क्रमबद्ध किया जा सकता है ताकि शीर्ष पड़ोस सन्निहित हों
- बहुपक्षीय ग्राफ़, शीर्षों के दो से अधिक उपसमूहों के लिए द्विभाज्य ग्राफ का सामान्यीकरण
- समता ग्राफ़, द्विभाज्य ग्राफ का सामान्यीकरण जिसमें समान दो बिंदुओं के बीच प्रत्येक दो प्रेरित पथों में समान समता होती है
- अर्ध-द्विपक्षीय ग्राफ़, प्रकार का स्टीनर ट्री समस्या उदाहरण जिसमें टर्मिनल स्वतंत्र समुच्चय बनाते हैं, जो सन्निकटन एल्गोरिदम की अनुमति देता है जो द्विभाज्य ग्राफ के लिए सामान्यीकरण करता है
- विभाजित ग्राफ ़, ग्राफ़ जिसमें शीर्षों को दो उपसमूहों में विभाजित किया जा सकता है, जिनमें से स्वतंत्र है और दूसरा समूह है
- निषिद्ध उपसमूहों वाले द्विभाज्य ग्राफ में किनारों की अधिकतम संख्या पर ज़ारांकिविज़ समस्या
संदर्भ
- ↑ Diestel, Reinard (2005), Graph Theory, Graduate Texts in Mathematics, Springer, ISBN 978-3-642-14278-9, archived from the original on 2011-04-09, retrieved 2012-02-27
- ↑ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press, ISBN 9780521593458.
- ↑ 3.0 3.1 3.2 Asratian, Denley & Häggkvist (1998), p. 7.
- ↑ 4.0 4.1 4.2 Scheinerman, Edward R. (2012), Mathematics: A Discrete Introduction (3rd ed.), Cengage Learning, p. 363, ISBN 9780840049421.
- ↑ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, Discrete Mathematics And Its Applications, vol. 53, CRC Press, p. 223, ISBN 9781584888000.
- ↑ Wasserman, Stanley; Faust, Katherine (1994), Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, pp. 299–302, ISBN 9780521387071.
- ↑ Niedermeier, Rolf (2006), Invitation to Fixed Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 20–21, ISBN 978-0-19-856607-6
- ↑ Bracey, Robert (2012), "On the graphical interpretation of Herod's year 3 coins", in Jacobson, David M.; Kokkinos, Nikos (eds.), Judaea and Rome in Coins 65 BCE – 135 CE: Papers Presented at the International Conference hosted by Spink, 13th – 14th September 2010, Spink & Son, pp. 65–84
- ↑ Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, pp. 136–137, ISBN 978-0-387-74640-1. 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.
- ↑ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID 10788524.
- ↑ Asratian, Denley & Häggkvist (1998), p. 11.
- ↑ Archdeacon, D.; Debowsky, M.; Dinitz, J.; Gavlas, H. (2004), "Cycle systems in the complete bipartite graph minus a one-factor", Discrete Mathematics, 284 (1–3): 37–43, doi:10.1016/j.disc.2003.11.021.
- ↑ Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.
- ↑ Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.
- ↑ Bang-Jensen, Jørgen; Gutin, Gregory (2001), Digraphs: Theory, Algorithms and Applications (PDF) (1st ed.), p. 25, ISBN 9781852332686, archived (PDF) from the original on 2023-01-02, retrieved 2023-01-02
- ↑ Woodall, D. R. (1990), "A proof of McKee's Eulerian-bipartite characterization", Discrete Mathematics, 84 (2): 217–220, doi:10.1016/0012-365X(90)90380-Z, MR 1071664
- ↑ Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, p. 53, ISBN 9780521458979.
- ↑ Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok, 38: 116–119.
- ↑ Gross, Jonathan L.; Yellen, Jay (2005), Graph Theory and Its Applications, Discrete Mathematics And Its Applications (2nd ed.), CRC Press, p. 568, ISBN 9781584885054.
- ↑ Chartrand, Gary; Zhang, Ping (2012), A First Course in Graph Theory, Courier Dover Publications, pp. 189–190, ISBN 9780486483689.
- ↑ Béla Bollobás (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 165, ISBN 9780387984889.
- ↑ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070, CiteSeerX 10.1.1.111.7265, doi:10.4007/annals.2006.164.51, S2CID 119151552.
- ↑ Lovász, László (2014), Combinatorial Problems and Exercises (2nd ed.), Elsevier, p. 281, ISBN 9780080933092
- ↑ Asratian, Denley & Häggkvist (1998), p. 17.
- ↑ A. A. Sapozhenko (2001) [1994], "Hypergraph", Encyclopedia of Mathematics, EMS Press
- ↑ Brualdi, Richard A.; Harary, Frank; Miller, Zevi (1980), "Bigraphs versus digraphs via matrices", Journal of Graph Theory, 4 (1): 51–73, doi:10.1002/jgt.3190040107, MR 0558453. Brualdi et al. credit the idea for this equivalence to Dulmage, A. L.; Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Canadian Journal of Mathematics, 10: 517–534, doi:10.4153/CJM-1958-052-0, MR 0097069, S2CID 123363425.
- ↑ Sedgewick, Robert (2004), Algorithms in Java, Part 5: Graph Algorithms (3rd ed.), Addison Wesley, pp. 109–111.
- ↑ Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, Addison Wesley, pp. 94–97.
- ↑ Eppstein, David (2009), "Testing bipartiteness of geometric intersection graphs", ACM Transactions on Algorithms, 5 (2): Art. 15, arXiv:cs.CG/0307023, doi:10.1145/1497290.1497291, MR 2561751, S2CID 60496.
- ↑ Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355, S2CID 363248
- ↑ Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, CiteSeerX 10.1.1.112.6357, doi:10.1016/j.orl.2003.10.009, MR 2057781.
- ↑ Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", Journal of Computer and System Sciences, 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001
- ↑ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Assignments and Matchings", Network Flows: Theory, Algorithms, and Applications, Prentice Hall, pp. 461–509.
- ↑ Ahuja, Magnanti & Orlin (1993), p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."
- ↑ Hopcroft, John E.; Karp, Richard M. (1973), "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2 (4): 225–231, doi:10.1137/0202019.
- ↑ Ahuja, Magnanti & Orlin (1993), Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
- ↑ Robinson, Sara (April 2003), "Are Medical Students Meeting Their (Best Possible) Match?" (PDF), SIAM News (3): 36, archived from the original (PDF) on 2016-11-18, retrieved 2012-08-27.
- ↑ Dulmage & Mendelsohn (1958).
- ↑ Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, p. 638, ISBN 9780471648000.
- ↑ Moon (2005), p. 686.
- ↑ Cassandras, Christos G.; Lafortune, Stephane (2007), Introduction to Discrete Event Systems (2nd ed.), Springer, p. 224, ISBN 9780387333328.
- ↑ Grünbaum, Branko (2009), Configurations of Points and Lines, Graduate Studies in Mathematics, vol. 103, American Mathematical Society, p. 28, ISBN 9780821843086.