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

Revision as of 08:36, 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]
एम और एन शीर्षों पर पूर्ण द्विदलीय ग्राफ, के द्वारा निरूपित_n,mद्विदलीय ग्राफ है $G=(U,V,E)$ , जहां U और V क्रमशः m और n आकार के असंयुक्त सेट हैं, और E, U के प्रत्येक शीर्ष को V के सभी शीर्षों से जोड़ता है। यह इस प्रकार है कि K_m,nएमएन किनारे हैं।^[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)$ आकार का (0,1) मैट्रिक्स है $|U|\times |V|$ इसमें आसन्न शीर्षों के प्रत्येक जोड़े के लिए और गैर-आसन्न शीर्षों के लिए शून्य है।^[24] द्विदलीय ग्राफ़, हाइपरग्राफ़ और निर्देशित ग्राफ़ के बीच समानता का वर्णन करने के लिए द्विआसन्नता मैट्रिक्स का उपयोग किया जा सकता है।

हाइपरग्राफ संयोजी संरचना है, जिसमें अप्रत्यक्ष ग्राफ की तरह, शीर्ष और किनारे होते हैं, लेकिन जिसमें किनारों में बिल्कुल दो समापन बिंदु होने के बजाय शीर्षों का मनमाना सेट हो सकता है। द्विदलीय ग्राफ $(U,V,E)$ जिसमें हाइपरग्राफ को मॉडल करने के लिए उपयोग किया जा सकता है $U$ हाइपरग्राफ के शीर्षों का समुच्चय है, $V$ हाइपरएज का समुच्चय है, और $E$ में हाइपरग्राफ शीर्ष से किनारा होता है $v$ हाइपरग्राफ किनारे तक $e$ बिलकुल कब $v$ के अंतिम बिंदुओं में से है $e$ . इस पत्राचार के तहत, द्विदलीय ग्राफ़ के द्विआसन्नता मैट्रिक्स वास्तव में संबंधित हाइपरग्राफ के घटना मैट्रिक्स हैं। द्विदलीय ग्राफ और हाइपरग्राफ के बीच इस पत्राचार के विशेष मामले के रूप में, किसी भी मल्टीग्राफ (ग्राफ जिसमें समान दो शीर्षों के बीच दो या दो से अधिक किनारे हो सकते हैं) को हाइपरग्राफ के रूप में व्याख्या किया जा सकता है जिसमें कुछ हाइपरएज में समापन बिंदुओं के समान सेट होते हैं, और द्विदलीय ग्राफ द्वारा दर्शाया गया है जिसमें एकाधिक आसन्नताएं नहीं हैं और जिसमें द्विविभाजन के तरफ के सभी शीर्षों की डिग्री (ग्राफ सिद्धांत) दो है।^[25] निकटवर्ती मैट्रिक्स की समान पुनर्व्याख्या का उपयोग निर्देशित ग्राफ़ (लेबल वाले शीर्षों की दी गई संख्या पर, स्व-लूप की अनुमति) और संतुलित द्विदलीय ग्राफ़ के बीच एक-से-पत्राचार दिखाने के लिए किया जा सकता है, जिसमें दोनों तरफ समान संख्या में कोने होते हैं। द्विविभाजन. के लिए, निर्देशित ग्राफ के आसन्न मैट्रिक्स के साथ $n$ शीर्ष आकार का कोई भी (0,1) मैट्रिक्स हो सकता है $n\times n$ , जिसे फिर द्विदलीय ग्राफ के आसन्न मैट्रिक्स के रूप में पुनः व्याख्या किया जा सकता है $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]

@@ Line 6: / Line 6: @@
   | 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|[[हेवुड ग्राफ]] द्विदलीय है।]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, एक द्विदलीय ग्राफ (या बिग्राफ) एक ग्राफ (असतत गणित) है जिसका शीर्ष (ग्राफ सिद्धांत) को दो [[असंयुक्त सेट]]ों और स्वतंत्र सेट (ग्राफ सिद्धांत) में विभाजित किया जा सकता है। <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
+[[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
   | first1 = Armen S.
@@ Line 31: / Line 31: @@
   | title = Mathematics: A Discrete Introduction
   | 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
+अक्सर कोई लिखता है <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
   | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
@@ Line 43: / Line 43: @@
   | url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
   | volume = 53
-  | 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> द्विनियमित ग्राफ कहलाता है।
+  | year = 2008}}.</ref> इस मामले में, <math>(U,V,E)</math> नोटेशन विशेष द्विविभाजन को निर्दिष्ट करने में सहायक होता है जो किसी एप्लिकेशन में महत्वपूर्ण हो सकता है। अगर <math>|U|=|V|</math>, अर्थात, यदि दो उपसमुच्चयों की [[प्रमुखता]] समान है, तो <math>G</math> संतुलित द्विदलीय ग्राफ कहलाता है।<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> यदि द्विविभाजन के ही तरफ के सभी शीर्षों की [[डिग्री (ग्राफ सिद्धांत)]] समान है, तो <math>G</math> द्विनियमित ग्राफ कहलाता है।
 ==उदाहरण==
-वस्तुओं के दो अलग-अलग वर्गों के बीच [[विषम संबंध]] मॉडलिंग करते समय, द्विदलीय ग्राफ़ अक्सर स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए, फुटबॉल खिलाड़ियों और क्लबों का एक ग्राफ, एक खिलाड़ी और एक क्लब के बीच बढ़त के साथ, यदि खिलाड़ी उस क्लब के लिए खेला है, एक संबद्धता नेटवर्क का एक प्राकृतिक उदाहरण है, जो [[सामाजिक नेटवर्क विश्लेषण]] में उपयोग किया जाने वाला एक प्रकार का द्विदलीय ग्राफ है।<ref>{{citation
+वस्तुओं के दो अलग-अलग वर्गों के बीच [[विषम संबंध]] मॉडलिंग करते समय, द्विदलीय ग्राफ़ अक्सर स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए, फुटबॉल खिलाड़ियों और क्लबों का ग्राफ, खिलाड़ी और क्लब के बीच बढ़त के साथ, यदि खिलाड़ी उस क्लब के लिए खेला है, संबद्धता नेटवर्क का प्राकृतिक उदाहरण है, जो [[सामाजिक नेटवर्क विश्लेषण]] में उपयोग किया जाने वाला प्रकार का द्विदलीय ग्राफ है।<ref>{{citation
   | last1 = Wasserman | first1 = Stanley
   | author-link1= Stanley Wasserman
@@ Line 59: / Line 59: @@
   | volume = 8
   | 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=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
+* एम और एन शीर्षों पर पूर्ण द्विदलीय ग्राफ, के द्वारा निरूपित<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
   | last2 = Debowsky | first2 = M.
@@ Line 76: / Line 76: @@
   | year = 2004| doi-access = free
   }}.</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>
+* [[हाइपरक्यूब ग्राफ]]़, आंशिक क्यूब्स और [[माध्यिका ग्राफ]]़ द्विदलीय हैं। इन ग्राफ़ों में, शीर्षों को [[बिटवेक्टर]]ों द्वारा इस तरह से लेबल किया जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल यदि संबंधित बिटवेक्टर ही स्थिति में भिन्न हों। उन शीर्षों को अलग करके द्विविभाजन बनाया जा सकता है जिनके बिटवेक्टर में विषम संख्या वाले शीर्षों से इकाइयों की संख्या सम है। पेड़ और वर्गालेख माध्यिका ग्राफ़ के उदाहरण बनाते हैं, और प्रत्येक माध्यिका ग्राफ़ [[आंशिक घन]] है।<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 83: / Line 83: @@
 ===लक्षणीकरण===
 द्विदलीय ग्राफ़ को कई अलग-अलग तरीकों से चित्रित किया जा सकता है:
-* एक अप्रत्यक्ष ग्राफ़ द्विदलीय है यदि और केवल तभी जब इसमें कोई चक्र (ग्राफ़ सिद्धांत) शामिल न हो।<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
+* अप्रत्यक्ष ग्राफ़ द्विदलीय है यदि और केवल तभी जब इसमें कोई चक्र (ग्राफ़ सिद्धांत) शामिल न हो।<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
 | first1 = Jørgen
@@ Line 99: / Line 99: @@
 | url-status = live
 }}</ref>
-* एक ग्राफ़ द्विदलीय है यदि और केवल यदि वह 2-रंगीय है, (अर्थात इसकी वर्णिक संख्या 2 से कम या उसके बराबर है)।<ref name="adh98-7"/>* एक ग्राफ द्विदलीय होता है यदि और केवल यदि प्रत्येक किनारा विषम संख्या में [[कट (ग्राफ सिद्धांत)]] से संबंधित हो, किनारों के न्यूनतम उपसमूह जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।<ref>{{citation
+* ग्राफ़ द्विदलीय है यदि और केवल यदि वह 2-रंगीय है, (अर्थात इसकी वर्णिक संख्या 2 से कम या उसके बराबर है)।<ref name="adh98-7"/>* ग्राफ द्विदलीय होता है यदि और केवल यदि प्रत्येक किनारा विषम संख्या में [[कट (ग्राफ सिद्धांत)]] से संबंधित हो, किनारों के न्यूनतम उपसमूह जिनके हटाने से ग्राफ के घटकों की संख्या बढ़ जाती है।<ref>{{citation
   | last = Woodall | first = D. R.
   | doi = 10.1016/0012-365X(90)90380-Z
@@ Line 109: / Line 109: @@
   | volume = 84
   | year = 1990| doi-access = free
-  }}</ref> * एक ग्राफ़ द्विदलीय है यदि और केवल यदि ग्राफ़ का वर्णक्रमीय ग्राफ़ सिद्धांत सममित है।<ref>{{citation
+  }}</ref> * ग्राफ़ द्विदलीय है यदि और केवल यदि ग्राफ़ का वर्णक्रमीय ग्राफ़ सिद्धांत सममित है।<ref>{{citation
   | last = Biggs | first = Norman
   | edition = 2nd
@@ Line 139: / Line 139: @@
   | title = Graph Theory and Its Applications
   | 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
   | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
@@ Line 149: / Line 149: @@
   | year = 2012}}.</ref> इस समानता को कोनिग के प्रमेय के साथ जोड़ने से यह तथ्य सामने आता है कि, द्विदलीय ग्राफ़ में, न्यूनतम किनारे कवर का आकार अधिकतम स्वतंत्र सेट के आकार के बराबर होता है, और न्यूनतम किनारे कवर का आकार और न्यूनतम शीर्ष कवर का आकार होता है शीर्षों की संख्या के बराबर है.
-संबंधित परिणामों का एक अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विदलीय ग्राफ़, प्रत्येक द्विदलीय ग्राफ़ का [[पूरक (ग्राफ सिद्धांत)]], प्रत्येक द्विदलीय ग्राफ़ का रेखा ग्राफ़, और प्रत्येक द्विदलीय ग्राफ़ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विदलीय ग्राफ़ की पूर्णता देखना आसान है (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) लेकिन द्विदलीय ग्राफ़ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का एक और पुनर्कथन है। यह उन परिणामों में से एक था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया।<ref>{{citation|title=Modern Graph Theory
+संबंधित परिणामों का अन्य वर्ग पूर्ण ग्राफ़ से संबंधित है: प्रत्येक द्विदलीय ग्राफ़, प्रत्येक द्विदलीय ग्राफ़ का [[पूरक (ग्राफ सिद्धांत)]], प्रत्येक द्विदलीय ग्राफ़ का रेखा ग्राफ़, और प्रत्येक द्विदलीय ग्राफ़ के रेखा ग्राफ़ का पूरक, सभी परिपूर्ण हैं। द्विदलीय ग्राफ़ की पूर्णता देखना आसान है (उनकी रंगीन संख्या दो है और उनका अधिकतम क्लिक आकार भी दो है) लेकिन द्विदलीय ग्राफ़ के पूरक (ग्राफ़ सिद्धांत) की पूर्णता कम तुच्छ है, और कोनिग के प्रमेय का और पुनर्कथन है। यह उन परिणामों में से था जिसने सही ग्राफ़ की प्रारंभिक परिभाषा को प्रेरित किया।<ref>{{citation|title=Modern Graph Theory
 |volume= 184 |series= Graduate Texts in Mathematics
 |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
+[[मजबूत परफेक्ट ग्राफ प्रमेय]] के अनुसार, परफेक्ट ग्राफ में द्विदलीय ग्राफ के समान [[निषिद्ध ग्राफ लक्षण वर्णन]] होता है: ग्राफ द्विदलीय होता है यदि और केवल तभी जब इसमें सबग्राफ के रूप में कोई विषम चक्र न हो, और ग्राफ तभी सही होता है जब इसमें कोई विषम चक्र न हो। प्रेरित उपसमूह के रूप में कोई विषम चक्र या उसका पूरक (ग्राफ़ सिद्धांत) नहीं। द्विदलीय ग्राफ़, द्विदलीय ग्राफ़ के रेखा ग्राफ़, और उनके पूरक मजबूत पूर्ण ग्राफ़ प्रमेय के प्रमाण में उपयोग किए जाने वाले पूर्ण ग्राफ़ के पांच बुनियादी वर्गों में से चार बनाते हैं।<ref>{{citation
   | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
   | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
@@ Line 169: / Line 169: @@
 ===डिग्री===
-एक शीर्ष के लिए, आसन्न शीर्षों की संख्या को शीर्ष की डिग्री (ग्राफ सिद्धांत) कहा जाता है और इसे दर्शाया जाता है <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>\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>U</math> और <math>V</math>. उदाहरण के लिए, संपूर्ण द्विदलीय ग्राफ K<sub>3,5</sub> डिग्री अनुक्रम है <math>(5,5,5),(3,3,3,3,3)</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> आकार का (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>
+हाइपरग्राफ संयोजी संरचना है, जिसमें अप्रत्यक्ष ग्राफ की तरह, शीर्ष और किनारे होते हैं, लेकिन जिसमें किनारों में बिल्कुल दो समापन बिंदु होने के बजाय शीर्षों का मनमाना सेट हो सकता है। द्विदलीय ग्राफ <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
+निकटवर्ती मैट्रिक्स की समान पुनर्व्याख्या का उपयोग [[निर्देशित ग्राफ]]़ (लेबल वाले शीर्षों की दी गई संख्या पर, स्व-लूप की अनुमति) और संतुलित द्विदलीय ग्राफ़ के बीच एक-से-पत्राचार दिखाने के लिए किया जा सकता है, जिसमें दोनों तरफ समान संख्या में कोने होते हैं। द्विविभाजन. के लिए, निर्देशित ग्राफ के आसन्न मैट्रिक्स के साथ {{mvar|n}} शीर्ष आकार का कोई भी (0,1) मैट्रिक्स हो सकता है <math>n\times n</math>, जिसे फिर द्विदलीय ग्राफ के आसन्न मैट्रिक्स के रूप में पुनः व्याख्या किया जा सकता है {{mvar|n}} इसके द्विभाजन के प्रत्येक तरफ शीर्ष।<ref>{{citation
   | last1 = Brualdi | first1 = Richard A.
   | last2 = Harary | first2 = Frank | author2-link = Frank Harary
@@ Line 205: / Line 205: @@
 ===द्विपक्षीयता का परीक्षण===
-यह परीक्षण करना संभव है कि क्या कोई ग्राफ द्विदलीय है, और [[गहराई-पहली खोज]] का उपयोग करके, [[रैखिक समय]] में या तो दो-रंग (यदि यह द्विदलीय है) या एक विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो गहराई-प्रथम खोज वन में उसके मूल रंग से भिन्न हो, गहराई-प्रथम-खोज वन के [[प्रीऑर्डर ट्रैवर्सल]] में रंग निर्दिष्ट किया जाए। यह आवश्यक रूप से फैले हुए जंगल को दो-रंग प्रदान करेगा जिसमें शीर्षों को उनके माता-पिता से जोड़ने वाले किनारे शामिल होंगे, लेकिन यह कुछ गैर-वन किनारों को ठीक से रंग नहीं सकता है। गहराई-प्रथम खोज वन में, प्रत्येक गैर-वन किनारे के दो समापन बिंदुओं में से एक दूसरे समापन बिंदु का पूर्वज होता है, और जब गहराई की पहली खोज इस प्रकार के किनारे की खोज करती है तो उसे जांचना चाहिए कि इन दोनों शीर्षों के अलग-अलग रंग हैं। यदि वे ऐसा नहीं करते हैं, तो जंगल में पूर्वज से वंशज तक का पथ, बदरंग किनारे के साथ, एक विषम चक्र बनाता है, जिसे एल्गोरिदम से इस परिणाम के साथ लौटाया जाता है कि ग्राफ द्विदलीय नहीं है। हालाँकि, यदि एल्गोरिथ्म इस प्रकार के एक विषम चक्र का पता लगाए बिना समाप्त हो जाता है, तो प्रत्येक किनारे को उचित रूप से रंगीन होना चाहिए, और एल्गोरिथ्म रंग को इस परिणाम के साथ लौटाता है कि ग्राफ द्विदलीय है।<ref>{{citation
+यह परीक्षण करना संभव है कि क्या कोई ग्राफ द्विदलीय है, और [[गहराई-पहली खोज]] का उपयोग करके, [[रैखिक समय]] में या तो दो-रंग (यदि यह द्विदलीय है) या विषम चक्र (यदि यह नहीं है) लौटाना संभव है। मुख्य विचार यह है कि प्रत्येक शीर्ष को वह रंग निर्दिष्ट किया जाए जो गहराई-प्रथम खोज वन में उसके मूल रंग से भिन्न हो, गहराई-प्रथम-खोज वन के [[प्रीऑर्डर ट्रैवर्सल]] में रंग निर्दिष्ट किया जाए। यह आवश्यक रूप से फैले हुए जंगल को दो-रंग प्रदान करेगा जिसमें शीर्षों को उनके माता-पिता से जोड़ने वाले किनारे शामिल होंगे, लेकिन यह कुछ गैर-वन किनारों को ठीक से रंग नहीं सकता है। गहराई-प्रथम खोज वन में, प्रत्येक गैर-वन किनारे के दो समापन बिंदुओं में से दूसरे समापन बिंदु का पूर्वज होता है, और जब गहराई की पहली खोज इस प्रकार के किनारे की खोज करती है तो उसे जांचना चाहिए कि इन दोनों शीर्षों के अलग-अलग रंग हैं। यदि वे ऐसा नहीं करते हैं, तो जंगल में पूर्वज से वंशज तक का पथ, बदरंग किनारे के साथ, विषम चक्र बनाता है, जिसे एल्गोरिदम से इस परिणाम के साथ लौटाया जाता है कि ग्राफ द्विदलीय नहीं है। हालाँकि, यदि एल्गोरिथ्म इस प्रकार के विषम चक्र का पता लगाए बिना समाप्त हो जाता है, तो प्रत्येक किनारे को उचित रूप से रंगीन होना चाहिए, और एल्गोरिथ्म रंग को इस परिणाम के साथ लौटाता है कि ग्राफ द्विदलीय है।<ref>{{citation
   | last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
   | edition = 3rd
@@ Line 212: / Line 212: @@
   | title = Algorithms in Java, Part 5: Graph Algorithms
   | year = 2004}}.</ref>
-वैकल्पिक रूप से, एक समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब एक शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला एक किनारा मौजूद होता है, तो यह किनारा चौड़ाई-प्रथम खोज वन में पथों के साथ मिलकर अपने दो अंतिम बिंदुओं को उनके निम्नतम सामान्य पूर्वज से जोड़ता है अजीब चक्र. यदि एल्गोरिथ्म इस तरह से एक विषम चक्र को खोजे बिना समाप्त हो जाता है, तो उसे एक उचित रंग मिल गया होगा, और सुरक्षित रूप से यह निष्कर्ष निकाला जा सकता है कि ग्राफ द्विदलीय है।<ref>{{citation
+वैकल्पिक रूप से, समान प्रक्रिया का उपयोग गहराई-प्रथम खोज के स्थान पर चौड़ाई-प्रथम खोज के साथ किया जा सकता है। पुनः, प्रत्येक नोड को चौड़ाई-प्रथम क्रम में, खोज वन में उसके मूल के विपरीत रंग दिया गया है। यदि, जब शीर्ष को रंगा जाता है, तो उसे उसी रंग के साथ पहले से रंगे हुए शीर्ष से जोड़ने वाला किनारा मौजूद होता है, तो यह किनारा चौड़ाई-प्रथम खोज वन में पथों के साथ मिलकर अपने दो अंतिम बिंदुओं को उनके निम्नतम सामान्य पूर्वज से जोड़ता है अजीब चक्र. यदि एल्गोरिथ्म इस तरह से विषम चक्र को खोजे बिना समाप्त हो जाता है, तो उसे उचित रंग मिल गया होगा, और सुरक्षित रूप से यह निष्कर्ष निकाला जा सकता है कि ग्राफ द्विदलीय है।<ref>{{citation
   | last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
   | last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
@@ Line 219: / Line 219: @@
   | title = Algorithm Design
   | year = 2006}}.</ref>
-के [[प्रतिच्छेदन ग्राफ]]़ के लिए <math>n</math> [[यूक्लिडियन विमान]] में [[रेखा खंड]]ों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ द्विदलीय है और समय में दो-रंग या एक विषम चक्र लौटाता है <math>O(n\log n)</math>, भले ही ग्राफ स्वयं तक हो सकता है <math>O\left(n^2\right)</math> किनारों.<ref>
+के [[प्रतिच्छेदन ग्राफ]]़ के लिए <math>n</math> [[यूक्लिडियन विमान]] में [[रेखा खंड]]ों या अन्य सरल आकृतियों से, यह परीक्षण करना संभव है कि क्या ग्राफ द्विदलीय है और समय में दो-रंग या विषम चक्र लौटाता है <math>O(n\log n)</math>, भले ही ग्राफ स्वयं तक हो सकता है <math>O\left(n^2\right)</math> किनारों.<ref>
 {{citation
   | last = Eppstein | first = David | author-link = David Eppstein
@@ Line 237: / Line 237: @@
 ===विषम चक्र अनुप्रस्थ===
 {{main|Odd cycle transversal}}
-[[File:Odd Cycle Transversal of size 2.png|thumb|आकार 2 के एक विषम चक्र अनुप्रस्थ वाला एक ग्राफ: दो नीले निचले शीर्षों को हटाने से एक द्विदलीय ग्राफ बनता है।]][[विषम चक्र अनुप्रस्थ]] एक एनपी-पूर्ण [[ कलन विधि ]] समस्या है जो ग्राफ G = (V,E) और एक संख्या k दिए जाने पर पूछती है कि क्या k शीर्षों का एक सेट मौजूद है, जिसे G से हटाने पर परिणामी ग्राफ द्विदलीय हो जाएगा।<ref name=yannakakis1978node>{{citation
+[[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
   | contribution = Node-and edge-deletion NP-complete problems
@@ Line 246: / Line 246: @@
   | title-link = Symposium on Theory of Computing | s2cid = 363248
 | doi-access = free
-  }}</ref> समस्या पैरामीटरीकृत जटिलता | निश्चित-पैरामीटर ट्रैक्टेबल है, जिसका अर्थ है कि एक एल्गोरिदम है जिसका चलने का समय ग्राफ के आकार के बहुपद फ़ंक्शन द्वारा k के बड़े फ़ंक्शन से गुणा किया जा सकता है।<ref name=reed2004finding>{{citation
+  }}</ref> समस्या पैरामीटरीकृत जटिलता | निश्चित-पैरामीटर ट्रैक्टेबल है, जिसका अर्थ है कि एल्गोरिदम है जिसका चलने का समय ग्राफ के आकार के बहुपद फ़ंक्शन द्वारा k के बड़े फ़ंक्शन से गुणा किया जा सकता है।<ref name=reed2004finding>{{citation
   | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
   | last2 = Smith | first2 = Kaleigh
@@ Line 258: / Line 258: @@
   | volume = 32
   | 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
+किनारे द्विदलीकरण समस्या ग्राफ को द्विदलीय बनाने के लिए जितना संभव हो उतना कम किनारों को हटाने की एल्गोरिथम समस्या है और यह ग्राफ संशोधन एल्गोरिदम में भी महत्वपूर्ण समस्या है। यह समस्या भी निश्चित-पैरामीटर सुव्यवस्थित है, और इसे समय पर हल किया जा सकता है <math display="inline">O\left(2^k m^2\right)</math>,<ref name=guo2006compression>{{citation
   | last1 = Guo | first1 = Jiong
   | last2 = Gramm | first2 = Jens
@@ Line 278: / Line 278: @@
 ===मिलान===
 {{main|Matching (graph theory)}}
-एक ग्राफ़ में मिलान (ग्राफ़ सिद्धांत) उसके किनारों का एक उपसमुच्चय है, जिनमें से कोई भी दो एक समापन बिंदु साझा नहीं करते हैं। बहुपद समय एल्गोरिदम मिलान पर कई एल्गोरिथम समस्याओं के लिए जाना जाता है, जिसमें अधिकतम मिलान (एक मिलान ढूंढना जो जितना संभव हो उतने किनारों का उपयोग करता है), [[अधिकतम वजन मिलान]] और [[स्थिर विवाह]] शामिल है।<ref>{{citation
+ग्राफ़ में मिलान (ग्राफ़ सिद्धांत) उसके किनारों का उपसमुच्चय है, जिनमें से कोई भी दो समापन बिंदु साझा नहीं करते हैं। बहुपद समय एल्गोरिदम मिलान पर कई एल्गोरिथम समस्याओं के लिए जाना जाता है, जिसमें अधिकतम मिलान (मिलान ढूंढना जो जितना संभव हो उतने किनारों का उपयोग करता है), [[अधिकतम वजन मिलान]] और [[स्थिर विवाह]] शामिल है।<ref>{{citation
   | last1 = Ahuja | first1 = Ravindra K.
   | last2 = Magnanti | first2 = Thomas L.
@@ Line 288: / Line 288: @@
   | 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
+सरल उदाहरण के रूप में, मान लीजिए कि सेट <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
   |first        = Sara
@@ Line 302: / Line 302: @@
   |url-status     = dead
 }}.</ref>
-डलमेज-मेंडेलसोहन अपघटन द्विदलीय ग्राफ़ का एक संरचनात्मक अपघटन है जो अधिकतम मिलान खोजने में उपयोगी है।<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>
+डलमेज-मेंडेलसोहन अपघटन द्विदलीय ग्राफ़ का संरचनात्मक अपघटन है जो अधिकतम मिलान खोजने में उपयोगी है।<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>
 ==अतिरिक्त अनुप्रयोग==
-आधुनिक [[कोडिंग सिद्धांत]] में द्विदलीय ग्राफ़ का व्यापक रूप से उपयोग किया जाता है, विशेष रूप से चैनल से प्राप्त [[कोडवर्ड]] को डिकोड करने के लिए। [[कारक ग्राफ]] और टैनर ग्राफ़ इसके उदाहरण हैं। [[टान्नर ग्राफ]] एक द्विदलीय ग्राफ है जिसमें द्विविभाजन के एक तरफ के कोने एक कोडवर्ड के अंकों का प्रतिनिधित्व करते हैं, और दूसरी तरफ के कोने उन अंकों के संयोजन का प्रतिनिधित्व करते हैं जिनका कोडवर्ड में त्रुटियों के बिना शून्य होने की उम्मीद है।<ref>{{citation
+आधुनिक [[कोडिंग सिद्धांत]] में द्विदलीय ग्राफ़ का व्यापक रूप से उपयोग किया जाता है, विशेष रूप से चैनल से प्राप्त [[कोडवर्ड]] को डिकोड करने के लिए। [[कारक ग्राफ]] और टैनर ग्राफ़ इसके उदाहरण हैं। [[टान्नर ग्राफ]] द्विदलीय ग्राफ है जिसमें द्विविभाजन के तरफ के कोने कोडवर्ड के अंकों का प्रतिनिधित्व करते हैं, और दूसरी तरफ के कोने उन अंकों के संयोजन का प्रतिनिधित्व करते हैं जिनका कोडवर्ड में त्रुटियों के बिना शून्य होने की उम्मीद है।<ref>{{citation
   | last = Moon | first = Todd K.
   | isbn = 9780471648000
@@ Line 313: / Line 313: @@
   | title = Error Correction Coding: Mathematical Methods and Algorithms
   | 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
+कंप्यूटर विज्ञान में, [[पेट्री नेट]] गणितीय मॉडलिंग उपकरण है जिसका उपयोग समवर्ती प्रणालियों के विश्लेषण और सिमुलेशन में किया जाता है। सिस्टम को नोड्स के दो सेटों के साथ द्विदलीय निर्देशित ग्राफ के रूप में तैयार किया जाता है: स्थान नोड्स का सेट जिसमें संसाधन होते हैं, और इवेंट नोड्स का सेट जो संसाधनों को उत्पन्न और/या उपभोग करता है। नोड्स और किनारों पर अतिरिक्त बाधाएं हैं जो सिस्टम के व्यवहार को बाधित करती हैं। पेट्री नेट सिस्टम के व्यवहार के गणितीय प्रमाण की अनुमति देने के लिए द्विदलीय निर्देशित ग्राफ़ और अन्य गुणों का उपयोग करते हैं, साथ ही सिस्टम के सिमुलेशन के आसान कार्यान्वयन की अनुमति भी देते हैं।<ref>{{citation
   | last1 = Cassandras | first1 = Christos G.
   | last2 = Lafortune | first2 = Stephane
@@ Line 324: / Line 324: @@
   | url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224
   | year = 2007}}.</ref>
-[[प्रक्षेप्य ज्यामिति]] में, [[लेवी ग्राफ]]़ द्विदलीय ग्राफ़ का एक रूप है जिसका उपयोग किसी कॉन्फ़िगरेशन (ज्यामिति) में बिंदुओं और रेखाओं के बीच की घटनाओं को मॉडल करने के लिए किया जाता है। बिंदुओं और रेखाओं की ज्यामितीय संपत्ति के अनुरूप, प्रत्येक दो रेखाएं अधिकतम एक बिंदु पर मिलती हैं और प्रत्येक दो बिंदु एक ही रेखा से जुड़े होते हैं, लेवी ग्राफ़ में आवश्यक रूप से लंबाई चार का कोई चक्र नहीं होता है, इसलिए उनकी [[परिधि (ग्राफ़ सिद्धांत)]] अवश्य होनी चाहिए छह या अधिक हों.<ref>{{citation
+[[प्रक्षेप्य ज्यामिति]] में, [[लेवी ग्राफ]]़ द्विदलीय ग्राफ़ का रूप है जिसका उपयोग किसी कॉन्फ़िगरेशन (ज्यामिति) में बिंदुओं और रेखाओं के बीच की घटनाओं को मॉडल करने के लिए किया जाता है। बिंदुओं और रेखाओं की ज्यामितीय संपत्ति के अनुरूप, प्रत्येक दो रेखाएं अधिकतम बिंदु पर मिलती हैं और प्रत्येक दो बिंदु ही रेखा से जुड़े होते हैं, लेवी ग्राफ़ में आवश्यक रूप से लंबाई चार का कोई चक्र नहीं होता है, इसलिए उनकी [[परिधि (ग्राफ़ सिद्धांत)]] अवश्य होनी चाहिए छह या अधिक हों.<ref>{{citation
   | last = Grünbaum | first = Branko | author-link = Branko Grünbaum
   | isbn = 9780821843086
@@ Line 338: / Line 338: @@
 ==यह भी देखें==
 *द्विपक्षीय आयाम, पूर्ण द्विदलीय ग्राफ़ की न्यूनतम संख्या जिसका संघ दिया गया ग्राफ़ है
-*द्विपक्षीय दोहरा आवरण, किसी भी ग्राफ़ को उसके शीर्षों को दोगुना करके द्विदलीय ग्राफ़ में बदलने का एक तरीका
+*द्विपक्षीय दोहरा आवरण, किसी भी ग्राफ़ को उसके शीर्षों को दोगुना करके द्विदलीय ग्राफ़ में बदलने का तरीका
-*द्विपक्षीय हाइपरग्राफ, हाइपरग्राफ के लिए द्विदलीयता का एक सामान्यीकरण।
+*द्विपक्षीय हाइपरग्राफ, हाइपरग्राफ के लिए द्विदलीयता का सामान्यीकरण।
-*द्विपक्षीय मैट्रोइड, मैट्रोइड्स का एक वर्ग जिसमें द्विदलीय ग्राफ़ के [[ग्राफ़िक मैट्रोइड]] शामिल हैं
+*द्विपक्षीय मैट्रोइड, मैट्रोइड्स का वर्ग जिसमें द्विदलीय ग्राफ़ के [[ग्राफ़िक मैट्रोइड]] शामिल हैं
-*द्विपक्षीय नेटवर्क प्रक्षेपण, द्विदलीय नेटवर्क के बारे में जानकारी को संपीड़ित करने के लिए एक भार तकनीक
+*द्विपक्षीय नेटवर्क प्रक्षेपण, द्विदलीय नेटवर्क के बारे में जानकारी को संपीड़ित करने के लिए भार तकनीक
-*[[उत्तल द्विदलीय ग्राफ]], एक द्विदलीय ग्राफ जिसके शीर्षों को क्रमबद्ध किया जा सकता है ताकि शीर्ष पड़ोस सन्निहित हों
+*[[उत्तल द्विदलीय ग्राफ]], द्विदलीय ग्राफ जिसके शीर्षों को क्रमबद्ध किया जा सकता है ताकि शीर्ष पड़ोस सन्निहित हों
 *[[बहुपक्षीय ग्राफ]]़, शीर्षों के दो से अधिक उपसमूहों के लिए द्विदलीय ग्राफ़ का सामान्यीकरण
-*[[समता ग्राफ]]़, द्विदलीय ग्राफ़ का एक सामान्यीकरण जिसमें समान दो बिंदुओं के बीच प्रत्येक दो [[प्रेरित पथ]]ों में समान समता होती है
+*[[समता ग्राफ]]़, द्विदलीय ग्राफ़ का सामान्यीकरण जिसमें समान दो बिंदुओं के बीच प्रत्येक दो [[प्रेरित पथ]]ों में समान समता होती है
-*[[अर्ध-द्विपक्षीय ग्राफ]]़, एक प्रकार का स्टीनर ट्री समस्या उदाहरण जिसमें टर्मिनल एक स्वतंत्र सेट बनाते हैं, जो सन्निकटन एल्गोरिदम की अनुमति देता है जो द्विदलीय ग्राफ़ के लिए सामान्यीकरण करता है
+*[[अर्ध-द्विपक्षीय ग्राफ]]़, प्रकार का स्टीनर ट्री समस्या उदाहरण जिसमें टर्मिनल स्वतंत्र सेट बनाते हैं, जो सन्निकटन एल्गोरिदम की अनुमति देता है जो द्विदलीय ग्राफ़ के लिए सामान्यीकरण करता है
-*[[ विभाजित ग्राफ ]]़, एक ग्राफ़ जिसमें शीर्षों को दो उपसमूहों में विभाजित किया जा सकता है, जिनमें से एक स्वतंत्र है और दूसरा एक समूह है
+*[[ विभाजित ग्राफ ]]़, ग्राफ़ जिसमें शीर्षों को दो उपसमूहों में विभाजित किया जा सकता है, जिनमें से स्वतंत्र है और दूसरा समूह है
 *निषिद्ध उपसमूहों वाले द्विदलीय ग्राफ़ में किनारों की अधिकतम संख्या पर [[ज़ारांकिविज़ समस्या]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 08:36, 23 July 2023

Contents

उदाहरण