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

ग्राफ़ सिद्धांत के गणितीय अभ्यास में, एक अप्रत्यक्ष ग्राफ़ में एक समतुल्य या स्वतंत्र किनारा समुच्चय किनारों का एक समूह होता है, जिसमें सामान्य समुच्चय के शीर्ष नहीं होते हैं।^[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] और जिनके किनारे वैकल्पिक रूप से मिलान के रूप में होते है हैं और यह मिलान के रूप में नहीं होता है और इस प्रकार संवर्धित पथ एक वैकल्पिक पथ है, जो मुक्त (बेजोड़) शीर्षों से प्रारंभ होता है और समाप्त होता है। बर्ज की प्रमेयिका कहती है कि एक मेल खाने वाला 'M' के रूप में अधिकतम होता है यदि और केवल यदि 'M, के संबंध में कोई संवर्द्धन पथ नहीं है।

एक प्रेरित मिलान एक मिलान है जो एक प्रेरित सबग्राफ का किनारा समुच्चय के रूप में होता है।^[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 के भीतर दोनों समस्याएं सन्निकटन कलन विधि हो सकती हैं: बस एक मनमाना अधिकतम मिलान एम खोजें।^[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]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

परिभाषाएँ

गुण

मिलान बहुपद