मिलान (ग्राफ सिद्धांत): Difference between revisions

Revision as of 09:04, 9 May 2023

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

परिभाषाएँ

एक ग्राफ असतत गणित $G = (V, E),$ G में मेल खाने वाला M युग्‍मानूसार गैर-आसन्न किनारों का समुच्चय होता है , जिनमें से कोई भी लुप्पस (ग्राफ सिद्धांत) के रूप में नहीं होते है; अर्थात्, कोई भी दो किनारे उभयनिष्ठ शीर्षों को साझा नहीं करते हैं।

एक शीर्ष मिलान किया जाता है (या संतृप्त) यदि यह मिलान किनारों में से एक का समापन बिंदु है। अन्यथा शीर्ष बेजोड़ (या असंतृप्त) रूप में होता है।

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

एक अधिकतम मिलान, जिसे अधिकतम गणनांक मिलान के रूप में भी जाना जाता है,^[2]) एक मिलान जिसमें किनारों की सबसे बड़ी संभावित संख्या होती है कई अधिकतम मिलान हो सकते हैं। मिलान संख्या

\nu (G)

एक ग्राफ का

G

अधिकतम मिलान का आकार है। प्रत्येक अधिकतम मिलान अधिकतम होता है, लेकिन प्रत्येक अधिकतम मिलान अधिकतम मिलान नहीं होता है। निम्नलिखित आंकड़ा समान तीन ग्राफ़ में अधिकतम मिलान के उदाहरण दिखाता है।

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

\nu (G)\leq \rho (G)

. एक ग्राफ़ में केवल तभी पूर्ण मिलान हो सकता है जब ग्राफ़ में सम संख्या में कोने हों।

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

मेल खाते 'M को देखते हुए, एक वैकल्पिक पथ एक ऐसा पथ है जो एक बेजोड़ शिखर से प्रारंभ होता है^[3] और जिनके किनारे वैकल्पिक रूप से मिलान के हैं और मिलान के नहीं हैं। संवर्धित पथ एक वैकल्पिक पथ है जो मुक्त (बेजोड़) शीर्षों से प्रारंभ होता है और समाप्त होता है। बर्ज की प्रमेयिका कहती है कि एक मेल खाने वाला 'एम' अधिकतम है यदि और केवल यदि 'एम' के संबंध में कोई संवर्द्धन पथ नहीं है।

एक प्रेरित मिलान एक मिलान है जो एक प्रेरित सबग्राफ का किनारा समुच्चय है।^[4]

गुण

अलग-अलग शीर्षों के बिना किसी भी ग्राफ़ में, मिलान संख्या और किनारों को कवर करने वाली संख्या का योग शीर्षों की संख्या के बराबर होता है।^[5] यदि कोई पूर्ण मिलान है, तो मिलान संख्या और किनारे का कवर नंबर दोनों हैं $| V | / 2$ .

यदि $A$ और $B$ तब दो अधिकतम मिलान हैं $| A | \leq 2| B |$ और $| B | \leq 2| A |$ . इसे देखने के लिए, ध्यान दें कि प्रत्येक किनारे में $B \ A$ अधिकतम दो किनारों के निकट हो सकता है $A \ B$ क्योंकि $A$ एक मिलान है; इसके अतिरिक्त प्रत्येक किनारे में $A \ B$ में एक किनारे के निकट है $B \ A$ की अधिकतमता से $B$ , इस तरह

|A\setminus B|\leq 2|B\setminus A|.

आगे हम यह निष्कर्ष निकालते हैं

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.

विशेष रूप से, यह दर्शाता है कि कोई भी अधिकतम मिलान अधिकतम मिलान का 2-अनुमान है और न्यूनतम अधिकतम मिलान का 2-अनुमान भी है। यह असमानता तंग है: उदाहरण के लिए, यदि $G$ 3 किनारों और 4 शीर्षों वाला पथ है, न्यूनतम अधिकतम मिलान का आकार 1 है और अधिकतम मिलान का आकार 2 है।

हसनी मोनफेरेड और मल्लिक द्वारा एक ग्राफ की मिलान संख्या का एक वर्णक्रमीय लक्षण वर्णन निम्नानुसार दिया गया है: मान लीजिए $G$ एक ग्राफ़_ (असतत_गणित) पर रहें $n$ शिखर, और $\lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0$ होना $k$ विशिष्ट गैर-शून्य काल्पनिक संख्या जहां $2k\leq n$ . फिर की मिलान संख्या $G$ है $k$ यदि और केवल यदि (ए) एक वास्तविक तिरछा-सममित मैट्रिक्स है $A$ ग्राफ के साथ $G$ और अभिलक्षणिक मान $\pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}$ और $n-2k$ शून्य, और (बी) ग्राफ के साथ सभी वास्तविक तिरछा-सममित आव्यूह $G$ अधिक से अधिक है $2k$ गैर-शून्य अभिलक्षणिक मान ।^[6] ध्यान दें कि एक वास्तविक सममित या तिरछा-सममित मैट्रिक्स का (सरल) ग्राफ $A$ आदेश की $n$ है $n$ के गैर-विकर्ण प्रविष्टियों द्वारा दिए गए कोने और किनारे $A$ .

मिलान बहुपद

एक ग्राफ़ में के-एज मिलानों की संख्या का एक जनरेटिंग फ़ंक्शन मिलान बहुपद कहलाता है। मान लीजिए कि G एक ग्राफ है और m_kके-एज मिलानों की संख्या हो। G का एक मेल खाने वाला बहुपद है

\sum _{k\geq 0}m_{k}x^{k}.

एक अन्य परिभाषा मेल खाने वाले बहुपद को इस प्रकार देती है

\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},

जहाँ n ग्राफ में शीर्षों की संख्या है। प्रत्येक प्रकार के अपने उपयोग हैं; अधिक जानकारी के लिए मिलान बहुपदों पर लेख देखें।

कलन विधि और कम्प्यूटेशनल जटिलता

अधिकतम-गणनांक मिलान

संयोजन अनुकूलन में एक मूलभूत समस्या अधिकतम मिलान ढूंढ रही है। इस समस्या में ग्राफ़ के विभिन्न वर्गों के लिए विभिन्न कलन विधि हैं।

एक अभारित द्विदलीय ग्राफ में, अधिकतम गणनांक मिलान खोजने के लिए अनुकूलन समस्या है। समस्या को हॉपक्रॉफ्ट-कार्प कलन विधि द्वारा समय पर हल किया जाता है $O (\sqrt V E)$ समय, और मुख्य लेख में वर्णित द्विदलीय प्लेनर ग्राफ ़ जैसे ग्राफ़ के विशेष वर्गों के लिए अधिक कुशल यादृच्छिक कलन विधि , सन्निकटन कलन विधि और कलन विधि हैं।

अधिकतम वजन मिलान

एक भारित ग्राफ़ द्विदलीय ग्राफ़ में, अनुकूलन समस्या एक अधिकतम-भार मिलान खोजने के लिए है; एक न्यूनतम वजन मिलान खोजने के लिए एक दोहरी समस्या है। इस समस्या को अधिकांशतः 'अधिकतम भारित द्विपक्षीय मिलान' या 'असाइनमेंट समस्या' कहा जाता है। हंगेरियन कलन विधि असाइनमेंट समस्या को हल करता है और यह कॉम्बीनेटरियल ऑप्टिमाइज़ेशन कलन विधि की शुरुआत में से एक था। यह संवर्द्धन पथ कलन विधि में एक संशोधित लघुतम पथ खोज का उपयोग करता है। यदि इस चरण के लिए बेलमैन-फोर्ड कलन विधि का उपयोग किया जाता है, तो हंगेरियन कलन विधि का रनिंग टाइम बन जाता है $O(V^{2}E)$ , या किनारे की लागत को प्राप्त करने की क्षमता के साथ स्थानांतरित किया जा सकता है $O(V^{2}\log {V}+VE)$ दिज्क्स्ट्रा का कलन विधि और फाइबोनैचि हीप के साथ चलने का समय।^[7]

एक गैर-द्विपक्षीय भारित ग्राफ में, 'अधिकतम वजन मिलान' की समस्या को समय पर हल किया जा सकता है $O(V^{2}E)$ एडमंड्स के मैचिंग कलन विधि का उपयोग करना | एडमंड्स का ब्लॉसम एल्गोरिथम।

अधिकतम मिलान

एक साधारण ग्रीडी कलन विधि के साथ अधिकतम मिलान के रूप में पाया जाता है और इस प्रकार अधिकतम मिलान भी एक मिलान है और इसलिए बहुपद समय में सबसे बड़ा अधिकतम मिलान प्राप्त करना संभव होता है। चूंकि, 'न्यूनतम अधिकतम मिलान' खोजने के लिए कोई बहुपद-समय कलन विधि ज्ञात नहीं है, अर्थात एक अधिकतम मिलान जिसमें किनारों की सबसे छोटी संख्या के रूप में सम्मलित होता है।

K किनारों के साथ एक अधिकतम मिलान k किनारों के साथ बढ़त पर हावी होने वाला समुच्चय है। इसके विपरीत यदि हमें k किनारों के साथ एक न्यूनतम धार हावी समुच्चय दिया जाता है, तो हम बहुपद समय में k किनारों के साथ एक अधिकतम मिलान का निर्माण कर सकते हैं। इसलिए, न्यूनतम अधिकतम मिलान खोजने की समस्या अनिवार्य रूप से न्यूनतम किनारे पर हावी होने वाले समुच्चय को खोजने की समस्या के बराबर है।^[8] इन दोनों अनुकूलन समस्याओं को एनपी पूर्ण समस्या के रूप में जाना जाता है; इन समस्याओं के निर्णय संस्करण एनपी-पूर्ण समस्याओं के उत्कृष्ट उदाहरण के रूप में हैं।^[9] और इस प्रकार बहुपद समय में कारक 2 के भीतर दोनों समस्याएं सन्निकटन कलन विधि के रूप में हो सकती हैं बस एक यादृच्छिक अधिकतम मिलान M को खोजें।^[10]

गिनती की समस्याएं

किसी ग्राफ़ में मिलानों की संख्या को ग्राफ़ के कज़ुओ होसोया एक्स के रूप में जाना जाता है। द्विदलीय रेखांकन के लिए भी, इस मात्रा की गणना करने के लिए यह तीव्र-पी-पूर्ण के रूप में होता है।^[11] द्विदलीय ग्राफ़ में भी पूर्ण मिलान की गणना करना #P-पूर्ण है, क्योंकि एक स्वेच्छिक 0–1 मैट्रिक्स अन्य #P-पूर्ण समस्या के स्थायी (गणित) की गणना करता है और पूर्ण मिलान की संख्या की गणना करने के समान है दिए गए मैट्रिक्स को इसके बायडजेंसी मैट्रिक्स के रूप में है। चूँकि, द्विदलीय मिलानों की संख्या की गणना के लिए एक पूर्ण बहुपद समय यादृच्छिक सन्निकटन योजना के रूप में उपस्थित होता है।^[12] पीटर कास्टली द्वारा के एक उल्लेखनीय प्रमेय में कहा गया है कि एफकेटी कलन विधि के माध्यम से एक प्लेनर ग्राफ में सही मिलान की संख्या बहुपद समय में यथार्थ रूप से गणना की जा सकती है।

पूर्ण ग्राफ़ में पूर्ण मिलानों की संख्या K_n (n सम के साथ) दोहरे क्रमगुणन (n − 1)!! द्वारा दिया जाता है।^[13] पूर्ण ग्राफ़ में मिलानों की संख्या मिलानों को पूर्ण होने के लिए विवश किए बिना, टेलीफोन नंबर (गणित) द्वारा दी गई है।^[14]

सभी अधिकतम मिलान करने योग्य किनारों का पता लगाना

मिलान सिद्धांत में मौलिक समस्याओं में दिए गए ग्राफ़ में सभी किनारों को खोजना होता है, जिन्हें ग्राफ़ में अधिकतम मिलान तक बढ़ाया जा सकता है ऐसे किनारों को अधिकतम मिलान करने योग्य किनारे या अनुमत किनारे कहा जाता है। यह समस्या कलन विधि में सम्मलित हैं:

सामान्य रेखांकन के लिए समय में एक नियतात्मक कलन विधि $O(VE)$ और समय में एक यादृच्छिक कलन विधि ${\tilde {O}}(V^{2.376})$ के रूप में होती है.^[15]^[16]
द्विदलीय रेखांकन के लिए, यदि एक एकल अधिकतम मिलान पाया जाता है, तो नियतात्मक $O(V+E)$ .कलन विधि समय में चलता है ^[17]

ऑनलाइन द्विपक्षीय मिलान

मिलान के लिए एक ऑनलाइन कलन विधि विकसित करने की समस्या पर सबसे पहले 1990 में रिचर्ड एम. कार्प, उमेश वजीरानी और विजय वजीरानी ने विचार किया था।^[18] ऑनलाइन सेटिंग में, द्विदलीय ग्राफ के एक तरफ के नोड्स समय में पहुंचते हैं और या तो तुरंत ग्राफ के दूसरी तरफ से मिलान किया जाता है या छोड़ दिया जाता है और इस प्रकार यह सेक्रेटरी समस्या का एक स्वाभाविक रूप में सामान्यीकरण होता है और इसमें ऑनलाइन विज्ञापन नीलामियों के लिए अनुप्रयोग के रूप में होता है। यह यादृच्छिक आगमन मॉडल के साथ भारित अधिकतमकरण स्थितियों के लिए सबसे अच्छा ऑनलाइन कलन विधि के रूप में है, एक प्रतिस्पर्धी विश्लेषण ऑनलाइन कलन विधि $0.696$ . प्राप्त करता है^[19]

लक्षण

कोनिग के प्रमेय में कहा गया है कि द्विदलीय रेखांकन में अधिकतम मिलान न्यूनतम शीर्ष् कवर के बराबर होता है। इस परिणाम के माध्यम से, द्विदलीय रेखांकन के लिए बहुपद समय में न्यूनतम शीर्ष् कवर, अधिकतम स्वतंत्र समुच्चय और अधिकतम शीर्ष् बिक्लिक समस्याओं को हल किया जा सकता है।

हॉल का मैरिज प्रमेय द्विदलीय रेखांकन का एक लक्षण को वर्णन करता है जिसमें एक परिपूर्ण मिलान होता है और टुट्टे प्रमेय निर्गुण रेखांकन के लिए एक लक्षण को वर्णन करता है।

अनुप्रयोग

सामान्य रेखांकन में मिलान

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

द्विदलीय रेखांकन में मिलान

क्रमस्थापन प्रॉब्लम क्रमस्थापन के लिए दी गई आवश्यकताओं में से कक्षाओं के न्यूनतम समुच्चय को चुनने के बारे में है।
परिवहन सिद्धांत (गणित) में उप-समस्या के रूप में द्विदलीय मिलान के रूप में सम्मलित होता है।
सबग्राफ समरूपता समस्या में उप-समस्या के रूप में द्विदलीय मिलान के रूप में सम्मलित होता है।

यह भी देखें

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

संदर्भ

↑ "is_matching". NetworkX 2.8.2 documentation. Retrieved 2022-05-31. Each node is incident to at most one edge in the matching. The edges are said to be independent.
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
↑ "Preview".
↑ Cameron, Kathie (1989), "Induced matchings", Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987, Discrete Applied Mathematics, 24 (1–3): 97–102, doi:10.1016/0166-218X(92)90275-F, MR 1011265
↑ Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 2: 133–138.
↑ Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004, https://arxiv.org/abs/1602.03590
↑ Fredman, Michael L.; Tarjan, Robert Endre (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM, 34 (3): 596–615, doi:10.1145/28869.28874, S2CID 7904683
↑ Yannakakis, Mihalis; Gavril, Fanica (1980), "Edge dominating sets in graphs" (PDF), SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030.
↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1.
↑ Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also Minimum Edge Dominating Set and Minimum Maximal Matching in the web compendium.
↑ Leslie Valiant, The Complexity of Enumeration and Reliability Problems, SIAM J. Comput., 8(3), 410–421
↑ Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric (2008). "Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems". SIAM Journal on Computing. 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687. doi:10.1137/050644033. S2CID 755231.
↑ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
↑ Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology, 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918.
↑ Rabin, Michael O.; Vazirani, Vijay V. (1989), "Maximum matchings in general graphs through randomization", Journal of Algorithms, 10 (4): 557–567, doi:10.1016/0196-6774(89)90005-9
↑ Cheriyan, Joseph (1997), "Randomized ${\widetilde {O}}(M(|V|))$ algorithms for problems in matching theory", SIAM Journal on Computing, 26 (6): 1635–1655, doi:10.1137/S0097539793256223
↑ Tassa, Tamir (2012), "Finding all maximally-matchable edges in a bipartite graph", Theoretical Computer Science, 423: 50–58, doi:10.1016/j.tcs.2011.12.071
↑ Karp, Richard M.; Vazirani, Umesh V.; Vazirani, Vijay V. (1990). "An optimal algorithm for on-line bipartite matching" (PDF). Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990). pp. 352–358. doi:10.1145/100216.100262.
↑ Mahdian, Mohammad; Yan, Qiqi (2011). "Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs". कम्प्यूटिंग के सिद्धांत पर तैंतालीसवें वार्षिक एसीएम संगोष्ठी की कार्यवाही. pp. 597–606. doi:10.1145/1993636.1993716.
↑ See, e.g., Trinajstić, Nenad; Klein, Douglas J.; Randić, Milan (1986), "On some solved and unsolved problems of chemical graph theory", International Journal of Quantum Chemistry, 30 (S20): 699–742, doi:10.1002/qua.560300762.

अग्रिम पठन

Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001), Introduction to Algorithms (second ed.), MIT Press and McGraw–Hill, Chapter 26, pp. 643–700, ISBN 0-262-53196-8{{citation}}: CS1 maint: multiple names: authors list (link)
András Frank (2004). On Kuhn's Hungarian Method – A tribute from Hungary (PDF) (Technical report). Egerváry Research Group.
Michael L. Fredman and Robert E. Tarjan (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM, 34 (3): 595–615, doi:10.1145/28869.28874, S2CID 7904683.
S. J. Cyvin & Ivan Gutman (1988), Kekule Structures in Benzenoid Hydrocarbons, Springer-Verlag
Marek Karpinski and Wojciech Rytter (1998), Fast Parallel Algorithms for Graph Matching Problems, Oxford University Press, ISBN 978-0-19-850162-6

बाहरी संबंध

A graph library with Hopcroft–Karp and Push–Relabel-based maximum cardinality matching implementation

[NetworkX_2.8.2_documentation-1] "is_matching". NetworkX 2.8.2 documentation. Retrieved 2022-05-31. Each node is incident to at most one edge in the matching. The edges are said to be independent.

[2] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.

[3] "Preview".

[4] Cameron, Kathie (1989), "Induced matchings", Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987, Discrete Applied Mathematics, 24 (1–3): 97–102, doi:10.1016/0166-218X(92)90275-F, MR 1011265

[5] Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 2: 133–138.

[6] Keivan Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419, https://doi.org/10.1016/j.laa.2016.02.004, https://arxiv.org/abs/1602.03590

[Fredman87-7] Fredman, Michael L.; Tarjan, Robert Endre (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM, 34 (3): 596–615, doi:10.1145/28869.28874, S2CID 7904683

[8] Yannakakis, Mihalis; Gavril, Fanica (1980), "Edge dominating sets in graphs" (PDF), SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030.

[9] Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1.

[10] Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also Minimum Edge Dominating Set and Minimum Maximal Matching in the web compendium.

[11] Leslie Valiant, The Complexity of Enumeration and Reliability Problems, SIAM J. Comput., 8(3), 410–421

[12] Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric (2008). "Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems". SIAM Journal on Computing. 37 (5): 1429–1454. CiteSeerX 10.1.1.80.687. doi:10.1137/050644033. S2CID 755231.

[13] Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.

[14] Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology, 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, PMID 16201918.

[15] Rabin, Michael O.; Vazirani, Vijay V. (1989), "Maximum matchings in general graphs through randomization", Journal of Algorithms, 10 (4): 557–567, doi:10.1016/0196-6774(89)90005-9

[16] Cheriyan, Joseph (1997), "Randomized ${\widetilde {O}}(M(|V|))$ algorithms for problems in matching theory", SIAM Journal on Computing, 26 (6): 1635–1655, doi:10.1137/S0097539793256223

[17] Tassa, Tamir (2012), "Finding all maximally-matchable edges in a bipartite graph", Theoretical Computer Science, 423: 50–58, doi:10.1016/j.tcs.2011.12.071

[18] Karp, Richard M.; Vazirani, Umesh V.; Vazirani, Vijay V. (1990). "An optimal algorithm for on-line bipartite matching" (PDF). Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990). pp. 352–358. doi:10.1145/100216.100262.

[19] Mahdian, Mohammad; Yan, Qiqi (2011). "Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs". कम्प्यूटिंग के सिद्धांत पर तैंतालीसवें वार्षिक एसीएम संगोष्ठी की कार्यवाही. pp. 597–606. doi:10.1145/1993636.1993716.

[20] See, e.g., Trinajstić, Nenad; Klein, Douglas J.; Randić, Milan (1986), "On some solved and unsolved problems of chemical graph theory", International Journal of Quantum Chemistry, 30 (S20): 699–742, doi:10.1002/qua.560300762.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

@@ Line 65: / Line 65: @@
 [[संयोजन अनुकूलन]] में एक मूलभूत समस्या अधिकतम मिलान ढूंढ रही है। इस समस्या में ग्राफ़ के विभिन्न वर्गों के लिए विभिन्न कलन विधि हैं।
-एक अभारित द्विदलीय ग्राफ में, [[अधिकतम कार्डिनैलिटी मिलान|अधिकतम गणनांक मिलान]] खोजने के लिए अनुकूलन समस्या है। समस्या को [[हॉपक्रॉफ्ट-कार्प एल्गोरिथम]] द्वारा समय पर हल किया जाता है {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} समय, और मुख्य लेख में वर्णित द्विदलीय [[ प्लेनर ग्राफ |प्लेनर ग्राफ]] ़ जैसे ग्राफ़ के विशेष वर्गों के लिए अधिक कुशल [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] , सन्निकटन कलन विधि और कलन विधि हैं।
+एक अभारित द्विदलीय ग्राफ में, [[अधिकतम कार्डिनैलिटी मिलान|अधिकतम गणनांक मिलान]] खोजने के लिए अनुकूलन समस्या है। समस्या को [[हॉपक्रॉफ्ट-कार्प एल्गोरिथम|हॉपक्रॉफ्ट-कार्प]] कलन विधि द्वारा समय पर हल किया जाता है {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} समय, और मुख्य लेख में वर्णित द्विदलीय [[ प्लेनर ग्राफ |प्लेनर ग्राफ]] ़ जैसे ग्राफ़ के विशेष वर्गों के लिए अधिक कुशल [[यादृच्छिक एल्गोरिदम|यादृच्छिक कलन विधि]] , सन्निकटन कलन विधि और कलन विधि हैं।
 === अधिकतम वजन मिलान ===
 {{Main|अधिकतम वजन मिलान}}
-एक भारित ग्राफ़ द्विदलीय ग्राफ़ में, अनुकूलन समस्या एक अधिकतम-भार मिलान खोजने के लिए है; एक न्यूनतम वजन मिलान खोजने के लिए एक दोहरी समस्या है। इस समस्या को अधिकांशतः 'अधिकतम भारित द्विपक्षीय मिलान' या 'असाइनमेंट समस्या' कहा जाता है। [[हंगेरियन एल्गोरिथम]] असाइनमेंट समस्या को हल करता है और यह कॉम्बीनेटरियल ऑप्टिमाइज़ेशन कलन विधि की शुरुआत में से एक था। यह संवर्द्धन पथ एल्गोरिथम में एक संशोधित लघुतम पथ खोज का उपयोग करता है। यदि इस चरण के लिए बेलमैन-फोर्ड कलन विधि का उपयोग किया जाता है, तो हंगेरियन एल्गोरिथम का रनिंग टाइम बन जाता है <math>O(V^2 E)</math>, या किनारे की लागत को प्राप्त करने की क्षमता के साथ स्थानांतरित किया जा सकता है <math>O(V^2 \log{V} + V E)</math> [[दिज्क्स्ट्रा का एल्गोरिथ्म|दिज्क्स्ट्रा का कलन विधि]] और फाइबोनैचि हीप के साथ चलने का समय।<ref name="Fredman87">{{citation|last1=Fredman|first1=Michael L.|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=[[Journal of the ACM]]|volume=34|issue=3|pages=596–615|year=1987|doi=10.1145/28869.28874|last2=Tarjan|first2=Robert Endre|s2cid=7904683}}</ref>
+एक भारित ग्राफ़ द्विदलीय ग्राफ़ में, अनुकूलन समस्या एक अधिकतम-भार मिलान खोजने के लिए है; एक न्यूनतम वजन मिलान खोजने के लिए एक दोहरी समस्या है। इस समस्या को अधिकांशतः 'अधिकतम भारित द्विपक्षीय मिलान' या 'असाइनमेंट समस्या' कहा जाता है। [[हंगेरियन एल्गोरिथम|हंगेरियन]] कलन विधि असाइनमेंट समस्या को हल करता है और यह कॉम्बीनेटरियल ऑप्टिमाइज़ेशन कलन विधि की शुरुआत में से एक था। यह संवर्द्धन पथ कलन विधि में एक संशोधित लघुतम पथ खोज का उपयोग करता है। यदि इस चरण के लिए बेलमैन-फोर्ड कलन विधि का उपयोग किया जाता है, तो हंगेरियन कलन विधि का रनिंग टाइम बन जाता है <math>O(V^2 E)</math>, या किनारे की लागत को प्राप्त करने की क्षमता के साथ स्थानांतरित किया जा सकता है <math>O(V^2 \log{V} + V E)</math> [[दिज्क्स्ट्रा का एल्गोरिथ्म|दिज्क्स्ट्रा का कलन विधि]] और फाइबोनैचि हीप के साथ चलने का समय।<ref name="Fredman87">{{citation|last1=Fredman|first1=Michael L.|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=[[Journal of the ACM]]|volume=34|issue=3|pages=596–615|year=1987|doi=10.1145/28869.28874|last2=Tarjan|first2=Robert Endre|s2cid=7904683}}</ref>
-एक गैर-द्विपक्षीय भारित ग्राफ में, '[[अधिकतम वजन मिलान]]' की समस्या को समय पर हल किया जा सकता है <math>O(V^{2}E)</math> एडमंड्स के मैचिंग एल्गोरिथम का उपयोग करना | एडमंड्स का ब्लॉसम एल्गोरिथम।
+एक गैर-द्विपक्षीय भारित ग्राफ में, '[[अधिकतम वजन मिलान]]' की समस्या को समय पर हल किया जा सकता है <math>O(V^{2}E)</math> एडमंड्स के मैचिंग कलन विधि का उपयोग करना | एडमंड्स का ब्लॉसम एल्गोरिथम।
 === अधिकतम मिलान ===
-एक साधारण लालची एल्गोरिथम के साथ एक अधिकतम मिलान पाया जा सकता है। एक अधिकतम मिलान भी एक अधिकतम मिलान है, और इसलिए बहुपद समय में सबसे बड़ा अधिकतम मिलान प्राप्त करना संभव है। हालांकि, 'न्यूनतम अधिकतम मिलान' खोजने के लिए कोई बहुपद-समय कलन विधि ज्ञात नहीं है, अर्थात , एक अधिकतम मिलान जिसमें किनारों की सबसे छोटी संख्या सम्मलित है।
+एक साधारण ग्रीडी कलन विधि के साथ अधिकतम मिलान के रूप में पाया जाता है और इस प्रकार अधिकतम मिलान भी एक मिलान है और इसलिए बहुपद समय में सबसे बड़ा अधिकतम मिलान प्राप्त करना संभव होता है। चूंकि, 'न्यूनतम अधिकतम मिलान' खोजने के लिए कोई बहुपद-समय कलन विधि ज्ञात नहीं है, अर्थात एक अधिकतम मिलान जिसमें किनारों की सबसे छोटी संख्या के रूप में सम्मलित होता है।
-K किनारों के साथ एक अधिकतम मिलान k किनारों के साथ बढ़त पर हावी होने वाला  समुच्चय है। इसके विपरीत, यदि हमें k किनारों के साथ एक न्यूनतम धार हावी  समुच्चय दिया जाता है, तो हम बहुपद समय में k किनारों के साथ एक अधिकतम मिलान का निर्माण कर सकते हैं। इसलिए, न्यूनतम अधिकतम मिलान खोजने की समस्या अनिवार्य रूप से न्यूनतम किनारे पर हावी होने वाले  समुच्चय को खोजने की समस्या के बराबर है।<ref>{{citation
+K किनारों के साथ एक अधिकतम मिलान k किनारों के साथ बढ़त पर हावी होने वाला समुच्चय है। इसके विपरीत यदि हमें k किनारों के साथ एक न्यूनतम धार हावी  समुच्चय दिया जाता है, तो हम बहुपद समय में k किनारों के साथ एक अधिकतम मिलान का निर्माण कर सकते हैं। इसलिए, न्यूनतम अधिकतम मिलान खोजने की समस्या अनिवार्य रूप से न्यूनतम किनारे पर हावी होने वाले  समुच्चय को खोजने की समस्या के बराबर है।<ref>{{citation
   | first1=Mihalis | last1=Yannakakis
   | first2=Fanica | last2=Gavril
@@ Line 89: / Line 89: @@
   | issue=3
 | url=http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf
-  }}.</ref> इन दोनों अनुकूलन समस्याओं को [[ एनपी कठिन |एनपी कठिन]] के रूप में जाना जाता है; इन समस्याओं के निर्णय संस्करण एनपी-पूर्ण समस्याओं के उत्कृष्ट उदाहरण हैं।<ref>{{citation
+  }}.</ref> इन दोनों अनुकूलन समस्याओं को [[ एनपी कठिन |एनपी पूर्ण समस्या]] के रूप में जाना जाता है; इन समस्याओं के निर्णय संस्करण एनपी-पूर्ण समस्याओं के उत्कृष्ट उदाहरण के रूप में हैं।<ref>{{citation
   | last1=Garey | first1=Michael R. | author-link1=Michael R. Garey
   | last2=Johnson | first2=David S. | author-link2=David S. Johnson
@@ Line 96: / Line 96: @@
   | publisher = W.H. Freeman
   | isbn=0-7167-1045-5
-| title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix&nbsp;A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix&nbsp;A1.1.</ref> बहुपद समय में कारक 2 के भीतर दोनों समस्याएं सन्निकटन कलन विधि हो सकती हैं: बस एक मनमाना अधिकतम मिलान एम खोजें।<ref>{{citation
+| title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix&nbsp;A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix&nbsp;A1.1.</ref> और इस प्रकार बहुपद समय में कारक 2 के भीतर दोनों समस्याएं सन्निकटन कलन विधि के रूप में हो सकती हैं बस एक यादृच्छिक अधिकतम मिलान M को खोजें।<ref>{{citation
   | last1=Ausiello | first1=Giorgio
   | last2=Crescenzi | first2=Pierluigi
@@ Line 107: / Line 107: @@
   | year=2003
 }}. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also [http://www.nada.kth.se/~viggo/wwwcompendium/node13.html Minimum Edge Dominating Set] and [http://www.nada.kth.se/~viggo/wwwcompendium/node21.html Minimum Maximal Matching] in the [http://www.nada.kth.se/~viggo/wwwcompendium/ web compendium].</ref>
 === गिनती की समस्याएं ===
 {{main|होसोया सूचकांक}}
-किसी ग्राफ़ में मिलानों की संख्या को ग्राफ़ के [[ कज़ुओ होसोया एक्स |कज़ुओ होसोया एक्स]] के रूप में जाना जाता है। द्विदलीय रेखांकन के लिए भी, इस मात्रा की गणना करने के लिए यह तीव्र-पी-पूर्ण|#पी-पूर्ण है।<ref>[[Leslie Valiant]], ''The Complexity of Enumeration and Reliability Problems'',  SIAM J. Comput., 8(3), 410–421</ref> द्विदलीय ग्राफ़ में भी, पूर्ण मिलान की गणना करना भी #P-पूर्ण है, क्योंकि एक स्वेच्छिक 0–1 मैट्रिक्स (अन्य #P-पूर्ण समस्या) के [[स्थायी (गणित)]] की गणना करना, पूर्ण मिलान की संख्या की गणना करने के समान है दिए गए मैट्रिक्स को इसके [[बायडजेंसी मैट्रिक्स]] के रूप में द्विदलीय ग्राफ। चूँकि , द्विदलीय मिलानों की संख्या की गणना के लिए एक पूर्ण बहुपद समय यादृच्छिक सन्निकटन योजना उपस्थित है।<ref>{{cite journal
+किसी ग्राफ़ में मिलानों की संख्या को ग्राफ़ के [[ कज़ुओ होसोया एक्स |कज़ुओ होसोया एक्स]] के रूप में जाना जाता है। द्विदलीय रेखांकन के लिए भी, इस मात्रा की गणना करने के लिए यह तीव्र-पी-पूर्ण के रूप में होता है।<ref>[[Leslie Valiant]], ''The Complexity of Enumeration and Reliability Problems'',  SIAM J. Comput., 8(3), 410–421</ref> द्विदलीय ग्राफ़ में भी पूर्ण मिलान की गणना करना #P-पूर्ण है, क्योंकि एक स्वेच्छिक 0–1 मैट्रिक्स अन्य #P-पूर्ण समस्या के [[स्थायी (गणित)]] की गणना करता है और पूर्ण मिलान की संख्या की गणना करने के समान है दिए गए मैट्रिक्स को इसके [[बायडजेंसी मैट्रिक्स]] के रूप में है। चूँकि, द्विदलीय मिलानों की संख्या की गणना के लिए एक पूर्ण बहुपद समय यादृच्छिक सन्निकटन योजना के रूप में उपस्थित होता है।<ref>{{cite journal
 | last1        = Bezáková
 | first1       = Ivona
@@ Line 132: / Line 130: @@
 }}</ref> [[पीटर कास्टली द्वारा]] के एक उल्लेखनीय प्रमेय में कहा गया है कि [[एफकेटी एल्गोरिदम|एफकेटी कलन विधि]] के माध्यम से एक प्लेनर ग्राफ में सही मिलान की संख्या बहुपद समय में यथार्थ रूप से गणना की जा सकती है।
-पूर्ण ग्राफ़ में पूर्ण मिलानों की संख्या K<sub>''n''</sub> (n सम के साथ) दोहरे क्रमगुणन (n − 1)!! द्वारा दिया जाता है।<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref> पूर्ण ग्राफ़ में मिलानों की संख्या, मिलानों को पूर्ण होने के लिए विवश किए बिना, [[टेलीफोन नंबर (गणित)]] द्वारा दी गई है।<ref>{{citation
+पूर्ण ग्राफ़ में पूर्ण मिलानों की संख्या K<sub>''n''</sub> (n सम के साथ) दोहरे क्रमगुणन (n − 1)!! द्वारा दिया जाता है।<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref> पूर्ण ग्राफ़ में मिलानों की संख्या मिलानों को पूर्ण होने के लिए विवश किए बिना, [[टेलीफोन नंबर (गणित)]] द्वारा दी गई है।<ref>{{citation
   | last1 = Tichy | first1 = Robert F.
   | last2 = Wagner | first2 = Stephan
@@ Line 144: / Line 142: @@
   | volume = 12
   | year = 2005}}.</ref>
@@ Line 149: / Line 148: @@
 {{Main|अधिकतम मिलान करने योग्य किनारा}}
-मिलान सिद्धांत में मौलिक समस्याओं में से एक दिए गए ग्राफ़ में सभी किनारों को खोजना है जिन्हें ग्राफ़ में अधिकतम मिलान तक बढ़ाया जा सकता है (ऐसे किनारों को अधिकतम मिलान करने योग्य किनारे या अनुमत किनारे कहा जाता है)। इस समस्या के कलन विधि में सम्मलित हैं:
+मिलान सिद्धांत में मौलिक समस्याओं में  दिए गए ग्राफ़ में सभी किनारों को खोजना होता है, जिन्हें ग्राफ़ में अधिकतम मिलान तक बढ़ाया जा सकता है ऐसे किनारों को अधिकतम मिलान करने योग्य किनारे या अनुमत किनारे कहा जाता है। यह समस्या कलन विधि में सम्मलित हैं:
-* सामान्य रेखांकन के लिए, समय में एक नियतात्मक कलन विधि <math>O(VE)</math> और समय में एक यादृच्छिक कलन विधि <math>\tilde{O}(V^{2.376}) </math>.<ref>{{citation
+* सामान्य रेखांकन के लिए समय में एक नियतात्मक कलन विधि <math>O(VE)</math> और समय में एक यादृच्छिक कलन विधि <math>\tilde{O}(V^{2.376}) </math> के रूप में होती है.<ref>{{citation
 | last1 = Rabin | first1 = Michael O.
 | last2 = Vazirani | first2 = Vijay V.
@@ Line 171: / Line 170: @@
 | doi = 10.1137/S0097539793256223
 }}</ref>
-* द्विदलीय रेखांकन के लिए, यदि एक एकल अधिकतम मिलान पाया जाता है, तो नियतात्मक कलन विधि समय में चलता है <math>O(V+E)</math>.<ref>{{citation
+* द्विदलीय रेखांकन के लिए, यदि एक एकल अधिकतम मिलान पाया जाता है, तो नियतात्मक <math>O(V+E)</math>.कलन विधि समय में चलता है <ref>{{citation
 | last1 = Tassa | first1= Tamir
 | title = Finding all maximally-matchable edges in a bipartite graph
@@ Line 184: / Line 183: @@
 === ऑनलाइन द्विपक्षीय मिलान ===
-मिलान के लिए एक [[ ऑनलाइन एल्गोरिदम |ऑनलाइन कलन विधि]] विकसित करने की समस्या पर सबसे पहले 1990 में रिचर्ड एम. कार्प, [[उमेश वजीरानी]] और [[विजय वजीरानी]] ने विचार किया था।<ref>{{cite conference|last1=Karp|first1=Richard M.|author1-link=Richard M. Karp|last2=Vazirani|first2=Umesh V.|author2-link=Umesh Vazirani|last3=Vazirani|first3=Vijay V.|author3-link=Vijay Vazirani|contribution=An optimal algorithm for on-line bipartite matching|contribution-url=https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf|doi=10.1145/100216.100262|pages=352–358|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)|year=1990}}</ref> ऑनलाइन सेटिंग में, द्विदलीय ग्राफ के एक तरफ के नोड्स एक समय में एक पर पहुंचते हैं और या तो तुरंत ग्राफ के दूसरी तरफ से मिलान किया जाना चाहिए या छोड़ दिया जाना चाहिए। यह [[सचिव समस्या]] का एक स्वाभाविक सामान्यीकरण है और इसमें ऑनलाइन विज्ञापन नीलामियों के लिए आवेदन हैं। एक यादृच्छिक आगमन मॉडल के साथ भारित अधिकतमकरण स्थितियों े के लिए सबसे अच्छा ऑनलाइन कलन विधि , एक [[प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)|प्रतिस्पर्धी विश्लेषण (ऑनलाइन कलन विधि )]] प्राप्त करता है {{math|0.696}}.<ref>{{cite conference|last1=Mahdian|first1=Mohammad|last2=Yan|first2=Qiqi|doi=10.1145/1993636.1993716|title=कम्प्यूटिंग के सिद्धांत पर तैंतालीसवें वार्षिक एसीएम संगोष्ठी की कार्यवाही|pages=597–606|contribution=Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs|year=2011|doi-access=free}}</ref>
+मिलान के लिए एक [[ ऑनलाइन एल्गोरिदम |ऑनलाइन कलन विधि]] विकसित करने की समस्या पर सबसे पहले 1990 में रिचर्ड एम. कार्प, [[उमेश वजीरानी]] और [[विजय वजीरानी]] ने विचार किया था।<ref>{{cite conference|last1=Karp|first1=Richard M.|author1-link=Richard M. Karp|last2=Vazirani|first2=Umesh V.|author2-link=Umesh Vazirani|last3=Vazirani|first3=Vijay V.|author3-link=Vijay Vazirani|contribution=An optimal algorithm for on-line bipartite matching|contribution-url=https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf|doi=10.1145/100216.100262|pages=352–358|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)|year=1990}}</ref> ऑनलाइन सेटिंग में, द्विदलीय ग्राफ के एक तरफ के नोड्स समय में पहुंचते हैं और या तो तुरंत ग्राफ के दूसरी तरफ से मिलान किया जाता है या छोड़ दिया जाता है और इस प्रकार यह [[सचिव समस्या|सेक्रेटरी समस्या]] का एक स्वाभाविक  रूप में सामान्यीकरण होता है और इसमें ऑनलाइन विज्ञापन नीलामियों के लिए अनुप्रयोग के रूप में होता है। यह यादृच्छिक आगमन मॉडल के साथ भारित अधिकतमकरण स्थितियों  के लिए सबसे अच्छा ऑनलाइन कलन विधि के रूप में है, एक [[प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)|प्रतिस्पर्धी विश्लेषण ऑनलाइन कलन विधि]] {{math|0.696}}. प्राप्त करता है<ref>{{cite conference|last1=Mahdian|first1=Mohammad|last2=Yan|first2=Qiqi|doi=10.1145/1993636.1993716|title=कम्प्यूटिंग के सिद्धांत पर तैंतालीसवें वार्षिक एसीएम संगोष्ठी की कार्यवाही|pages=597–606|contribution=Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs|year=2011|doi-access=free}}</ref>
 == लक्षण ==
-कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय में कहा गया है कि द्विदलीय ग्राफ में, अधिकतम मिलान आकार में न्यूनतम [[वर्टेक्स कवर]] के बराबर होता है। इस परिणाम के माध्यम से, द्विदलीय रेखांकन के लिए बहुपद समय में न्यूनतम वर्टेक्स कवर, [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र]]  समुच्चय और अधिकतम वर्टेक्स बिक्लिक समस्याओं को हल किया जा सकता है।
+कोनिग के प्रमेय में कहा गया है कि द्विदलीय रेखांकन में अधिकतम मिलान न्यूनतम [[वर्टेक्स कवर|शीर्ष् कवर]] के बराबर होता है। इस परिणाम के माध्यम से, द्विदलीय रेखांकन के लिए बहुपद समय में न्यूनतम शीर्ष् कवर, [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र]]  समुच्चय और अधिकतम शीर्ष् बिक्लिक समस्याओं को हल किया जा सकता है।
-हॉल का विवाह प्रमेय द्विदलीय रेखांकन का एक लक्षण वर्णन प्रदान करता है जिसमें एक परिपूर्ण मिलान होता है और टुट्टे प्रमेय मनमाने रेखांकन के लिए एक लक्षण वर्णन प्रदान करता है।
+हॉल का मैरिज प्रमेय द्विदलीय रेखांकन का एक लक्षण को वर्णन करता है जिसमें एक परिपूर्ण मिलान होता है और टुट्टे प्रमेय निर्गुण रेखांकन के लिए एक लक्षण को वर्णन करता है।
 == अनुप्रयोग ==
 === सामान्य रेखांकन में मिलान ===
-* [[सुगंध]] की एक केकुले संरचना में इसके [[कंकाल सूत्र]] का सही मिलान होता है, जो [[रासायनिक संरचना]] में दोहरे बंधनों के स्थानों को दर्शाता है। इन संरचनाओं का नाम फ्रेडरिक अगस्त केकुले वॉन स्ट्रैडोनिट्ज़ के नाम पर रखा गया है, जिन्होंने दिखाया कि [[बेंजीन]] (ग्राफ़ सैद्धांतिक शब्दों में, एक 6-वर्टेक्स चक्र) को ऐसी संरचना दी जा सकती है।<ref>See, e.g., {{citation|title=On some solved and unsolved problems of chemical graph theory|last1=Trinajstić|first1=Nenad|author-link=Nenad Trinajstić|last2=Klein|first2=Douglas J.|last3=Randić|first3=Milan |author-link3=Milan Randić|journal=International Journal of Quantum Chemistry|year=1986|volume=30|issue=S20|pages=699–742|doi=10.1002/qua.560300762}}.</ref>
+* [[सुगंध|ऐरोमेटिक यौगिक]]  की केकुले संरचना में इसके [[कार्बन]] [[कंकाल सूत्र]] का सही मिलान होता है, जो [[रासायनिक संरचना]] में दोहरे बंधनों के स्थानों को दर्शाता है। इन संरचनाओं का नाम फ्रेडरिक अगस्त केकुले वॉन स्ट्रैडोनिट्ज़ के नाम पर रखा गया है, जिन्होंने दिखाया कि [[बेंजीन]] ग्राफ़ सैद्धांतिक शब्दों में एक 6 शीर्ष् चक्र को ऐसी संरचना दी जा सकती है।<ref>See, e.g., {{citation|title=On some solved and unsolved problems of chemical graph theory|last1=Trinajstić|first1=Nenad|author-link=Nenad Trinajstić|last2=Klein|first2=Douglas J.|last3=Randić|first3=Milan |author-link3=Milan Randić|journal=International Journal of Quantum Chemistry|year=1986|volume=30|issue=S20|pages=699–742|doi=10.1002/qua.560300762}}.</ref>
-* होसोया इंडेक्स गैर-खाली मिलानों की संख्या और एक जोड़ है; यह कार्बनिक यौगिकों के लिए [[कम्प्यूटेशनल रसायन विज्ञान]] और गणितीय रसायन विज्ञान जांच में प्रयोग किया जाता है।
+* होसोया इंडेक्स गैर-खाली मिलानों की संख्या का एक जोड़ है और इस प्रकार यह कार्बनिक यौगिकों के लिए [[कम्प्यूटेशनल रसायन विज्ञान]] और गणितीय रसायन विज्ञान जांच में प्रयोग किया जाता है।
 * [[चीनी डाकिया समस्या]] में एक उप-समस्या के रूप में एक न्यूनतम-भार पूर्ण मिलान खोजना सम्मलित है।
 === द्विदलीय रेखांकन में मिलान ===
-* [http://community.topcoder.com/stat?c=problem_statement&pm=2852&rd=5075 ग्रेजुएशन प्रॉब्लम] ग्रेजुएशन के लिए दी गई आवश्यकताओं में से कक्षाओं के न्यूनतम  समुच्चय को चुनने के बारे में है।
+* [http://community.topcoder.com/stat?c=problem_statement&pm=2852&rd=5075 क्रमस्थापन प्रॉब्लम]  क्रमस्थापन के लिए दी गई आवश्यकताओं में से कक्षाओं के न्यूनतम  समुच्चय को चुनने के बारे में है।
-* [[परिवहन सिद्धांत (गणित)]] में उप-समस्या के रूप में द्विदलीय मिलान सम्मलित है।
+* [[परिवहन सिद्धांत (गणित)]] में उप-समस्या के रूप में द्विदलीय मिलान  के रूप में सम्मलित होता है।
-* [[सबग्राफ समरूपता समस्या]] समस्या में उप-समस्या के रूप में द्विदलीय मिलान सम्मलित है।
+*[[सबग्राफ समरूपता समस्या]] में उप-समस्या के रूप में द्विदलीय मिलान  के रूप में सम्मलित होता है।
 == यह भी देखें ==
-* [[हाइपरग्राफ में मिलान]] - रेखांकन में मिलान का सामान्यीकरण।
+* [[हाइपरग्राफ में मिलान]] - रेखांकन में मिलान का सामान्यीकरण होता है।।
-* [[आंशिक मिलान]]।
+* [[आंशिक मिलान]] के रूप में होता है।
-* डलमेज-मेंडेलसोहन अपघटन, उपसमुच्चय में एक द्विदलीय ग्राफ के कोने का विभाजन, जैसे कि प्रत्येक किनारा एक पूर्ण मिलान से संबंधित है और केवल यदि इसके समापन बिंदु एक ही उपसमुच्चय से संबंधित हैं
+* डलमेज-मेंडेलसोहन अपघटन उपसमुच्चय में द्विदलीय ग्राफ के कोने का विभाजन किया जा सकता है, जैसे कि प्रत्येक किनारा एक पूर्ण मिलान से संबंधित होता है और केवल यदि इसके समापन बिंदु एक ही उपसमुच्चय से संबंधित हैं
-* [[ किनारे का रंग ]]ग्राफ के किनारों का मिलान में विभाजन
+* [[ किनारे का रंग ]]ग्राफ के किनारों का मिलान में विभाजन किया जा सकता है।
-* [[ मिलान रोकथाम | मिलान रोकथाम]] परफेक्ट मैचिंग को उपस्थित होने से रोकने के लिए किनारों की न्यूनतम संख्या को हटाना
+* [[ मिलान रोकथाम | मिलान रोकथाम]] परिपूर्ण मिलान को रोकने के लिए हटाने के लिए किनारों की न्यूनतम संख्या के रूप में होता है।
-* [[ इंद्रधनुष मिलान ]], बिना दोहराए रंग वाले एज-कलर्ड बाइपार्टाइट ग्राफ में मैचिंग
+* [[ इंद्रधनुष मिलान ]], इंद्रधनुष मिलान, दोहराए गए रंगों के साथ एक गहरे रंग के द्विपक्षीय ग्राफ में एक मिलान के रूप में होता है।
-* [[तिरछा-सममित ग्राफ]], एक प्रकार का ग्राफ जिसका उपयोग मिलान के लिए वैकल्पिक पथ खोजों को मॉडल करने के लिए किया जा सकता है
+* [[तिरछा-सममित ग्राफ]], एक प्रकार का ग्राफ जिसका उपयोग मिलान के लिए वैकल्पिक पथ खोज का मॉडल उपयोग करने के लिए किया जा सकता है
 * [[स्थिर मिलान]], एक मिलान जिसमें कोई भी दो तत्व एक दूसरे को अपने मेल खाने वाले भागीदारों के लिए पसंद नहीं करते हैं
-* स्वतंत्र शीर्ष समुच्चय, शीर्षों का एक समूह (किनारों के अतिरिक्त ) जिनमें से कोई भी दो एक दूसरे से सटे हुए नहीं हैं
+* स्वतंत्र शीर्ष समुच्चय, शीर्षों का एक समूह किनारों के अतिरिक्त जिनमें से कोई भी दो एक दूसरे से सटे हुए नहीं होते है
 * स्थिर विवाह समस्या स्थिर मिलान समस्या के रूप में भी जानी जाती है

Anonymous

Search

मिलान (ग्राफ सिद्धांत): Difference between revisions

Namespaces

More

Page actions

Revision as of 09:04, 9 May 2023

Contents

परिभाषाएँ

गुण

मिलान बहुपद