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

For दो रेखांकन की तुलना, see ग्राफ मिलान.

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

परिभाषाएँ

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

यदि मिलान किनारों का समापन बिंदु है। तो शीर्ष मिलान या संतृप्त रूप में होता है, अन्यथा इसका शीर्ष अतुल या असंतृप्त रूप में होता है।

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

अधिकतम मिलान, जिसे अधिकतम गणनांक मिलान के रूप में भी जाना जाता है,) मिलान जिसमें किनारों की सबसे बड़ी संभावित संख्या होती है कई अधिकतम मिलान हो सकते हैं। मिलान संख्या $\nu (G)$ ग्राफ का G अधिकतम मिलान का आकार है। प्रत्येक अधिकतम मिलान अधिकतम होता है, लेकिन प्रत्येक अधिकतम मिलान अधिकतम मिलान नहीं होता है। निम्नलिखित आंकड़ा समान तीन ग्राफ़ में अधिकतम मिलान के उदाहरण दिखाता है।

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

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

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

प्रेरित मिलान एक मिलान है जो प्रेरित उपग्राफ का किनारा समुच्चय के रूप में होता है ।

गुण

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

यदि A और B तब दो अधिकतम मिलान हैं |A| ≤ 2|B| और |B| ≤ 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 होता है।

विशेष रूप से, यह दर्शाता है कि कोई भी अधिकतम मिलान एक अधिकतम का 2-सन्निकटन और न्यूनतम अधिकतम मिलान का एक 2-सन्निकटन होता है

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

मिलान बहुपद

Main article: मिलान बहुपद

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

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

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

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

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

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

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

Main article: अधिकतम गणनांक मिलान

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

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

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

Main article: अधिकतम वजन मिलान

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

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

अधिकतम मिलान

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

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

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

Main article: होसोया सूचकांक

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

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

सभी मैक्सीमली मिलान किनारों का पता लगाना

Main article: मैक्सीमली मिलान किनारा

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

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

ऑनलाइन बाइपार्टाइट मिलान

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

लक्षण

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

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

अनुप्रयोग

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

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

बाइपार्टाइट रेखांकन में मिलान

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

यह भी देखें

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

अग्रिम पठन

1. 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
2. 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)
3. András Frank (2004). On Kuhn's Hungarian Method – A tribute from Hungary (PDF) (Technical report). Egerváry Research Group.
4. 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.
5. S. J. Cyvin & Ivan Gutman (1988), Kekule Structures in Benzenoid Hydrocarbons, Springer-Verlag
6. 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