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

File:Simple bipartite graph; no crossings.svg

Example of a bipartite graph without cycles

File:Biclique K 3 5 bicolor.svg

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

File:Heawood graph bipartite (bicolor).svg

हेवुड ग्राफ़ द्विभाज्य है।

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

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

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

उदाहरण

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

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

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

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

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

गुण

लक्षणीकरण

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

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

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

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

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

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

डिग्री

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

$\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) मैट्रिक्स है। इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए एक और गैर-आसन्न शीर्षों के लिए एक शून्य है। द्विभाज्य ग्राफ़, हाइपरग्राफ और निर्देशित ग्राफ़ के बीच समानता का वर्णन करने के लिए द्विआसन्नता मैट्रिक्स का उपयोग किया जा सकता है।।

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

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

एल्गोरिदम

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

यह परीक्षण करना संभव है कि क्या कोई ग्राफ़ द्विभाज्य है, और डेप्थ-फर्स्ट सर्च का उपयोग करके, रैखिक समय में तो दो-रंग (यदि यह द्विभाज्य है) या एक विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो डेप्थ-फर्स्ट सर्च फारेस्ट में उसके मूल रंग से भिन्न हो, डेप्थ-फर्स्ट-सर्च फारेस्ट के