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

Revision as of 15:07, 23 July 2023

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

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

Namespaces

More

Page actions

Revision as of 15:07, 23 July 2023

Contents

उदाहरण