द्विदलीय ग्राफ

Example of a bipartite graph without cycles

एम = 5 और एन = 3 के साथ पूर्ण द्विभाज्य ग्राफ

ग्राफ सिद्धांत के गणित क्षेत्र में, द्विभाज्य ग्राफ (या बिग्राफ) एक ऐसा ग्राफ (असतत गणित) है जिसके शीर्षों (ग्राफ सिद्धांत) को दो असंयुक्त समुच्चय और स्वतंत्र समुच्चय (ग्राफ सिद्धांत) $U$ और $V$ में विभाजित किया जा सकता है। अर्थात्, प्रत्येक वर्टेक्स (ग्राफ़ सिद्धांत) $U$ में एक शीर्ष को $V$ में एक से जोड़ता है। वर्टेक्स समुच्चय $U$ और $V$ को सामान्यतः ग्राफ़ के भाग कहा जाता है। समान रूप से, एक द्विभाज्य ग्राफ ऐसा ग्राफ है जिसमें कोई विषम-लंबाई चक्र (ग्राफ सिद्धांत) नहीं होता है।^[1]^[2]

दो समुच्चय $U$ और $V$ इसे ग्राफ़ को दो रंगों से रंगने के रूप में सोचा जा सकता है: यदि कोई सभी नोड्स को $U$ नीले रंग में रंगता है, और सभी नोड्स को $V$ लाल रंग में रंगता है, तो प्रत्येक किनारे पर भिन्न-भिन्न रंगों के समापन बिंदु होते हैं, जैसा कि ग्राफ़ रंग समस्या में आवश्यक है।^[3]^[4] इसके विपरीत, गैर-द्विपक्षीय ग्राफ़ के स्थिति में ऐसा रंग असंभव है, जैसे कि त्रिकोण: एक नोड को नीला और दूसरे को लाल रंग देने के बाद, त्रिकोण का तीसरा शीर्ष दोनों रंगों के शीर्षों से जुड़ा होता है, जिससे इसे किसी भी रंग को निर्दिष्ट करने से रोका जा सकता है।

एक द्विभाज्य ग्राफ़ को दर्शाने के लिए अधिकांश $G=(U,V,E)$ लिखा जाता है जिसके विभाजन में $U$ और $V$ भाग होते हैं, $E$ ग्राफ़ के किनारों को दर्शाता है। यदि एक द्विभाज्य ग्राफ जुड़ा हुआ ग्राफ़ नहीं है, तो इसमें से अधिक द्विविभाजन हो सकते हैं;^[5] इस स्थिति में, $(U,V,E)$ नोटेशन एक विशेष द्विविभाजन को निर्दिष्ट करने में सहायक होता है जो किसी अनुप्रयोग में महत्वपूर्ण हो सकता है। यदि $|U|=|V|$ , अर्थात, यदि दो उपसमुच्चयों में समान कार्डिनैलिटी है, तो $G$ को संतुलित द्विभाज्य ग्राफ कहा जाता है।^[3] यदि द्विविभाजन के एक ही तरफ के सभी शीर्षों की डिग्री (ग्राफ सिद्धांत) समान है, तो $G$ द्विविभाजन ग्राफ कहलाता है।

उदाहरण

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

एक अन्य उदाहरण जहां द्विभाज्य ग्राफ़ स्वाभाविक रूप से दिखाई देते हैं वह (एनपी-पूर्ण) रेलवे अनुकूलन समस्या है, जिसमें इनपुट ट्रेनों और उनके स्टॉप का एक शेड्यूल है, और लक्ष्य ट्रेन स्टेशनों का एक सेट जितना संभव हो उतना छोटा ढूंढना है जिससे प्रत्येक ट्रेन चुने हुए स्टेशनों में से कम से कम एक पर जाए। इस समस्या को एक द्विभाज्य ग्राफ़ में एक प्रमुख सेट समस्या के रूप में तैयार किया जा सकता है जिसमें प्रत्येक ट्रेन और प्रत्येक स्टेशन के लिए एक शीर्ष होता है और स्टेशन के प्रत्येक जोड़े और उस स्टेशन पर रुकने वाली ट्रेन के लिए एक किनारा होता है।^[7]

तीसरा उदाहरण मुद्राशास्त्र के शैक्षणिक क्षेत्र में है। प्राचीन सिक्के डिज़ाइन के दो सकारात्मक प्रभावों (सामने और पीछे) का उपयोग करके बनाए जाते हैं। मुद्राशास्त्री सिक्कों के उत्पादन को दर्शाने के लिए जो चार्ट बनाते हैं, वे द्विभाज्य ग्राफ होते हैं।^[8]

अधिक सारगर्भित उदाहरणों में निम्नलिखित सम्मिलित हैं:

प्रत्येक वृक्ष (ग्राफ़ सिद्धांत) द्विभाज्य है।^[4]
सम संख्या में शीर्षों वाले चक्र ग्राफ द्विभाज्य होते हैं।^[4]
प्रत्येक समतलीय ग्राफ, जिसके सभी फलकों की लंबाई सम है, द्विभाज्य है।^[9] इसके विशेष स्थिति ग्रिड ग्राफ और वर्गाकार ग्राफ़ हैं, जिनमें प्रत्येक आंतरिक फलक में 4 किनारे होते हैं और प्रत्येक आंतरिक शीर्ष पर चार या अधिक पड़ोसी होते हैं।^[10]
m और n शीर्षों पर पूर्ण द्विभाज्य ग्राफ, जिसे K_n,m द्वारा निरूपित किया जाता है, द्विभाज्य ग्राफ $G=(U,V,E)$ है, जहां U और V क्रमशः m और n आकार के असंयुक्त समुच्चय हैं, और E, U के प्रत्येक शीर्ष को V के सभी शीर्षों से जोड़ता है। यह इस प्रकार है कि K_m,n mn किनारे हैं।^[11] पूर्ण द्विभाज्य ग्राफ से निकटता से संबंधित क्राउन ग्राफ़ हैं, जो पूर्ण मिलान के किनारों को हटाकर पूर्ण द्विभाज्य ग्राफ से बनते हैं।^[12]
हाइपरक्यूब ग्राफ, आंशिक क्यूब्स और माध्यिका ग्राफ द्विभाज्य हैं। इन ग्राफ़ों में, शीर्षों को बिटवेक्टरों द्वारा इस प्रकार से लेबल किया जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल यदि संबंधित बिटवेक्टर ही स्थिति में भिन्न हों। उन शीर्षों को अलग करके द्विविभाजन बनाया जा सकता है जिनके बिटवेक्टर में विषम संख्या वाले शीर्षों से इकाइयों की संख्या सम है। ट्री और वर्गालेख माध्यिका ग्राफ़ के उदाहरण बनाते हैं, और प्रत्येक माध्यिका ग्राफ़ आंशिक घन है।^[13]

गुण

लक्षणीकरण

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

अप्रत्यक्ष ग्राफ़ द्विभाज्य है यदि और केवल तभी जब इसमें कोई चक्र (ग्राफ़ सिद्धांत) सम्मिलित नही होता हैं।^[14]^[15]
ग्राफ़ द्विभाज्य है यदि और केवल यदि वह 2-रंगीय है, (अर्थात इसकी वर्णिक संख्या 2 से कम या उसके समान है)।^[3]
ग्राफ द्विभाज्य होता है यदि और केवल यदि प्रत्येक वर्टेक्स विषम संख्या में कट (ग्राफ सिद्धांत) से संबंधित हो, किनारों के न्यूनतम उपग्राफ जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।^[16]
ग्राफ़ द्विभाज्य है यदि और केवल यदि ग्राफ़ का वर्णक्रमीय ग्राफ़ सिद्धांत सममित है।^[17]

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

द्विभाज्य ग्राफ में, न्यूनतम शीर्ष कवर का आकार अधिकतम मिलान के आकार के समान होता है; यह कोनिग का प्रमेय (ग्राफ सिद्धांत) है।^[18]^[19] इस प्रमेय का एक वैकल्पिक और समतुल्य रूप यह है कि अधिकतम स्वतंत्र समुच्चय का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के समान है। पृथक शीर्ष के बिना किसी भी ग्राफ़ में न्यूनतम किनारे कवर का आकार और अधिकतम मिलान का आकार शीर्षों की संख्या के समान होता है।^[20] इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, द्विभाज्य ग्राफ में, न्यूनतम किनारे कवर का आकार अधिकतम स्वतंत्र समुच्चय के आकार के समान होता है, और न्यूनतम किनारे कवर का आकार और न्यूनतम शीर्ष कवर का आकार शीर्षों की संख्या के समान होता है।

संबंधित परिणामों का एक अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विभाज्य ग्राफ, प्रत्येक द्विभाज्य ग्राफ का पूरक (ग्राफ सिद्धांत), प्रत्येक द्विभाज्य ग्राफ का रेखा ग्राफ़, और प्रत्येक द्विभाज्य ग्राफ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विभाज्य ग्राफ की पूर्णता देखना (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) आसान है किन्तु द्विभाज्य ग्राफ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का और पुनर्कथन है। यह उन परिणामों में से एक था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया था।^[21] पूर्ण ग्राफ़ के लाइन ग्राफ़ के पूरकों की पूर्णता कोनिग के प्रमेय का और पुनर्कथन है, और लाइन ग्राफ़ की पूर्णता स्वयं कोनिग के पहले के प्रमेय का पुनर्कथन है, कि प्रत्येक द्विभाज्य ग्राफ में अधिकतम डिग्री के बराबर रंगों की संख्या का उपयोग करके एक किनारे का रंग होता है।

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

डिग्री

किसी शीर्ष के लिए, आसन्न शीर्षों की संख्या को शीर्ष की डिग्री कहा जाता है और इसे $\deg(v)$ से दर्शाया जाता है। द्विभाज्य ग्राफ़ के लिए डिग्री योग सूत्र बताता है कि^[23]

\sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|\,.

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

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

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

द्विभाज्य ग्राफ $(U,V,E)$ का द्विआसन्नता मैट्रिक्स $|U|\times |V|$ आकार का एक (0,1) मैट्रिक्स है। इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए एक और गैर-आसन्न शीर्षों के लिए एक शून्य है।^[24] द्विभाज्य ग्राफ़, हाइपरग्राफ और निर्देशित ग्राफ़ के बीच समानता का वर्णन करने के लिए द्विआसन्नता मैट्रिक्स का उपयोग किया जा सकता है।।

हाइपरग्राफ एक संयोजी संरचना है, जिसमें एक अप्रत्यक्ष ग्राफ की तरह, शीर्ष और किनारे होते हैं, लेकिन जिसमें किनारों में बिल्कुल दो समापन बिंदु होने के बजाय शीर्षों का स्वैच्छिक सेट हो सकता है। हाइपरग्राफ को मॉडल करने के लिए एक द्विभाज्य ग्राफ $(U,V,E)$ का उपयोग किया जा सकता है जिसमें $U$ हाइपरग्राफ के शीर्षों का सेट है, $V$ हाइपरएज का सेट है, और $E$ में हाइपरग्राफ वर्टेक्स $v$ से हाइपरग्राफ किनारे $e$ तक एक किनारा होता है, ठीक उसी समय जब $v$ $e$ के अंतिम बिंदुओं में से एक होता है। इस पत्राचार के अनुसार, द्विभाज्य ग्राफ के द्विआसन्नता मैट्रिक्स वास्तव में संबंधित हाइपरग्राफ के घटना मैट्रिक्स हैं। द्विभाज्य ग्राफ और हाइपरग्राफ के बीच इस पत्राचार के विशेष स्थिति के रूप में, किसी भी मल्टीग्राफ (ग्राफ जिसमें समान दो शीर्षों के बीच दो या दो से अधिक किनारे हो सकते हैं) को हाइपरग्राफ के रूप में व्याख्या किया जा सकता है जिसमें कुछ हाइपरएज में समापन बिंदुओं के समान समुच्चय होते हैं, और द्विभाज्य ग्राफ द्वारा दर्शाया गया है जिसमें एकाधिक आसन्नताएं नहीं होती हैं और जिसमें द्विविभाजन के एक तरफ सभी कोने में डिग्री दो होती है।^[25]

निकटवर्ती मैट्रिक्स की समान पुनर्व्याख्या का उपयोग निर्देशित ग्राफ (लेबल वाले शीर्षों की दी गई संख्या पर, स्व-लूप की अनुमति) और संतुलित द्विभाज्य ग्राफ के बीच एक-से-पत्राचार दिखाने के लिए किया जा सकता है, जिसमें द्विविभाजन के दोनों किनारों पर समान संख्या में कोने होते हैं। क्योंकि, $n$ शीर्षों के साथ एक निर्देशित ग्राफ का आसन्न मैट्रिक्स $n\times n$ आकार का कोई भी (0,1) मैट्रिक्स हो सकता है, जिसे उसके द्विविभाजन के प्रत्येक पक्ष पर $n$ शीर्षों के साथ एक द्विभाज्य ग्राफ के आसन्न मैट्रिक्स के रूप में पुन: व्याख्या किया जा सकता है।^[26] इस निर्माण में, द्विभाज्य ग्राफ निर्देशित ग्राफ का द्विभाज्य दोहरा आवरण है।

एल्गोरिदम

द्विपक्षीयता का परीक्षण

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

वैकल्पिक रूप से, समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला वर्टेक्स मौजूद होता है, तो यह वर्टेक्स चौड़ाई-प्रथम खोज वन में पथों के साथ मिलकर अपने दो अंतिम बिंदुओं को उनके निम्नतम सामान्य पूर्वज से जोड़ता है अजीब चक्र. यदि एल्गोरिथ्म इस तरह से विषम चक्र को खोजे बिना समाप्त हो जाता है, तो उसे उचित रंग मिल गया होगा, और सुरक्षित रूप से यह निष्कर्ष निकाला जा सकता है कि ग्राफ द्विभाज्य है।^[28] के प्रतिच्छेदन ग्राफ़ के लिए $n$ यूक्लिडियन विमान में रेखा खंडों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ द्विभाज्य है और समय में दो-रंग या विषम चक्र लौटाता है $O(n\log n)$ , भले ही ग्राफ स्वयं तक हो सकता है $O\left(n^{2}\right)$ किनारों.^[29]

विषम चक्र अनुप्रस्थ

आकार 2 के विषम चक्र अनुप्रस्थ वाला ग्राफ: दो नीले निचले शीर्षों को हटाने से द्विभाज्य ग्राफ बनता है।

विषम चक्र अनुप्रस्थ एनपी-पूर्ण कलन विधि समस्या है जो ग्राफ G = (V,E) और संख्या k दिए जाने पर पूछती है कि क्या k शीर्षों का समुच्चय मौजूद है, जिसे G से हटाने पर परिणामी ग्राफ द्विभाज्य हो जाएगा।^[30] समस्या पैरामीटरीकृत जटिलता | निश्चित-पैरामीटर ट्रैक्टेबल है, जिसका अर्थ है कि एल्गोरिदम है जिसका चलने का समय ग्राफ के आकार के बहुपद फ़ंक्शन द्वारा k के बड़े फ़ंक्शन से गुणा किया जा सकता है।^[31] विषम चक्र अनुप्रस्थ नाम इस तथ्य से आता है कि ग्राफ द्विभाज्य होता है यदि और केवल तभी जब इसमें कोई विषम चक्र (ग्राफ सिद्धांत) न हो। इसलिए, द्विभाज्य ग्राफ प्राप्त करने के लिए ग्राफ से शीर्षों को हटाने के लिए, किसी को सभी विषम चक्रों को हिट करने की आवश्यकता होती है, या तथाकथित विषम चक्र ट्रांसवर्सल (कॉम्बिनेटरिक्स) समुच्चय ढूंढना होता है। उदाहरण में, ग्राफ़ के प्रत्येक विषम चक्र में नीला (सबसे निचला) शीर्ष होता है, इसलिए उन शीर्षों को हटाने से सभी विषम चक्र समाप्त हो जाते हैं और द्विभाज्य ग्राफ निकल जाता है।

किनारे द्विदलीकरण समस्या ग्राफ को द्विभाज्य बनाने के लिए जितना संभव हो उतना कम किनारों को हटाने की एल्गोरिथम समस्या है और यह ग्राफ संशोधन एल्गोरिदम में भी महत्वपूर्ण समस्या है। यह समस्या भी निश्चित-पैरामीटर सुव्यवस्थित है, और इसे समय पर हल किया जा सकता है ${\textstyle O\left(2^{k}m^{2}\right)}$ ,^[32] जहां k हटाए जाने वाले किनारों की संख्या है और m इनपुट ग्राफ़ में किनारों की संख्या है।

मिलान

ग्राफ़ में मिलान (ग्राफ़ सिद्धांत) उसके किनारों का उपसमुच्चय है, जिनमें से कोई भी दो समापन बिंदु साझा नहीं करते हैं। बहुपद समय एल्गोरिदम मिलान पर कई एल्गोरिथम समस्याओं के लिए जाना जाता है, जिसमें अधिकतम मिलान (मिलान ढूंढना जो जितना संभव हो उतने किनारों का उपयोग करता है), अधिकतम वजन मिलान और स्थिर विवाह सम्मिलित है।^[33] कई स्थितियों में, गैर-द्विपक्षीय ग्राफ़ की तुलना में मिलान समस्याओं को द्विभाज्य ग्राफ पर हल करना आसान होता है,^[34] और अधिकतम कार्डिनैलिटी मिलान के लिए हॉपक्रॉफ्ट-कार्प एल्गोरिदम जैसे कई मिलान एल्गोरिदम^[35] केवल द्विभाज्य इनपुट पर सही ढंग से काम करें।

सरल उदाहरण के रूप में, मान लीजिए कि समुच्चय $P$ सभी लोग समूह के बीच से नौकरी की तलाश कर रहे हैं $J$ नौकरियों की, सभी लोग सभी नौकरियों के लिए उपयुक्त नहीं हैं। इस स्थिति को द्विभाज्य ग्राफ के रूप में प्रतिरूपित किया जा सकता है $(P,J,E)$ जहां वर्टेक्स प्रत्येक नौकरी चाहने वाले को प्रत्येक उपयुक्त नौकरी से जोड़ता है।^[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 n^5/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.

बाहरी संबंध

[diestel2005graph-1] 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

[2] 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.

[adh98-7-3] 3.0 ^3.1 ^3.2 Asratian, Denley & Häggkvist (1998), p. 7.

[s12-4] 4.0 ^4.1 ^4.2 Scheinerman, Edward R. (2012), Mathematics: A Discrete Introduction (3rd ed.), Cengage Learning, p. 363, ISBN 9780840049421.

[5] Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, Discrete Mathematics And Its Applications, vol. 53, CRC Press, p. 223, ISBN 9781584888000.

[6] 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.

[niedermeier2006invitiation-7] 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

[bracey2012-8] 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

[9] 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.

[10] 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.

[11] Asratian, Denley & Häggkvist (1998), p. 11.

[12] 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.

[13] Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.

[14] 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.

[15] 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

[16] 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

[17] Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, p. 53, ISBN 9780521458979.

[18] Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok, 38: 116–119.

[19] Gross, Jonathan L.; Yellen, Jay (2005), Graph Theory and Its Applications, Discrete Mathematics And Its Applications (2nd ed.), CRC Press, p. 568, ISBN 9781584885054.

[20] Chartrand, Gary; Zhang, Ping (2012), A First Course in Graph Theory, Courier Dover Publications, pp. 189–190, ISBN 9780486483689.

[21] Béla Bollobás (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 165, ISBN 9780387984889.

[22] 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.

[23] Lovász, László (2014), Combinatorial Problems and Exercises (2nd ed.), Elsevier, p. 281, ISBN 9780080933092

[24] Asratian, Denley & Häggkvist (1998), p. 17.

[25] A. A. Sapozhenko (2001) [1994], "Hypergraph", Encyclopedia of Mathematics, EMS Press

[26] 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.

[27] Sedgewick, Robert (2004), Algorithms in Java, Part 5: Graph Algorithms (3rd ed.), Addison Wesley, pp. 109–111.

[28] Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, Addison Wesley, pp. 94–97.

[29] 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.

[yannakakis1978node-30] 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

[reed2004finding-31] 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.

[guo2006compression-32] 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

[33] 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.

[34] Ahuja, Magnanti & Orlin (1993), p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."

[35] Hopcroft, John E.; Karp, Richard M. (1973), "An n^5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2 (4): 225–231, doi:10.1137/0202019.

[36] Ahuja, Magnanti & Orlin (1993), Application 12.1 Bipartite Personnel Assignment, pp. 463–464.

[37] 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.

[38] Dulmage & Mendelsohn (1958).

[39] Moon, Todd K. (2005), Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, p. 638, ISBN 9780471648000.

[40] Moon (2005), p. 686.

[41] Cassandras, Christos G.; Lafortune, Stephane (2007), Introduction to Discrete Event Systems (2nd ed.), Springer, p. 224, ISBN 9780387333328.

[42] Grünbaum, Branko (2009), Configurations of Points and Lines, Graduate Studies in Mathematics, vol. 103, American Mathematical Society, p. 28, ISBN 9780821843086.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

Anonymous

Search

द्विदलीय ग्राफ

Namespaces

More

Page actions

Contents

उदाहरण