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

From Vigyanwiki
(Created page with "{{Short description|Set of edges without common vertices}} {{for|comparisons of two graphs|Graph matching}} ग्राफ़ सिद्धांत के गणिती...")
 
No edit summary
Line 16: Line 16:
:[[File:Maximal-matching.svg]]एक अधिकतम मिलान (अधिकतम-कार्डिनैलिटी मिलान के रूप में भी जाना जाता है<ref>Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>) एक मिलान है जिसमें किनारों की सबसे बड़ी संभव संख्या होती है। कई अधिकतम मिलान हो सकते हैं। मिलान संख्या <math>\nu(G)</math> एक ग्राफ का {{mvar|G}} अधिकतम मिलान का आकार है। प्रत्येक अधिकतम मिलान अधिकतम होता है, लेकिन प्रत्येक अधिकतम मिलान अधिकतम मिलान नहीं होता है। निम्नलिखित आंकड़ा समान तीन ग्राफ़ में अधिकतम मिलान के उदाहरण दिखाता है।
:[[File:Maximal-matching.svg]]एक अधिकतम मिलान (अधिकतम-कार्डिनैलिटी मिलान के रूप में भी जाना जाता है<ref>Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>) एक मिलान है जिसमें किनारों की सबसे बड़ी संभव संख्या होती है। कई अधिकतम मिलान हो सकते हैं। मिलान संख्या <math>\nu(G)</math> एक ग्राफ का {{mvar|G}} अधिकतम मिलान का आकार है। प्रत्येक अधिकतम मिलान अधिकतम होता है, लेकिन प्रत्येक अधिकतम मिलान अधिकतम मिलान नहीं होता है। निम्नलिखित आंकड़ा समान तीन ग्राफ़ में अधिकतम मिलान के उदाहरण दिखाता है।


:[[File:Maximum-matching-labels.svg]]एक पूर्ण मिलान वह मिलान है जो ग्राफ़ के सभी शीर्षों से मेल खाता है। अर्थात्, यदि ग्राफ़ का प्रत्येक शीर्ष मिलान के किनारे पर आपतन (ज्यामिति) हो, तो मिलान पूर्ण होता है। एक मिलान सही है अगर |E|=|V|/2। प्रत्येक पूर्ण मिलान अधिकतम होता है और इसलिए अधिकतम होता है। कुछ साहित्य में, पूर्ण मिलान शब्द का प्रयोग किया जाता है। उपरोक्त आकृति में, केवल भाग (बी) एक पूर्ण मिलान दिखाता है। एक पूर्ण मिलान न्यूनतम आकार का [[ किनारे का आवरण ]] भी है। इस प्रकार, अधिकतम मिलान का आकार न्यूनतम किनारे के कवर के आकार से बड़ा नहीं है: {{tmath|\nu(G) \le \rho(G)}}. एक ग्राफ़ में केवल तभी पूर्ण मिलान हो सकता है जब ग्राफ़ में सम संख्या में कोने हों।
:[[File:Maximum-matching-labels.svg]]एक पूर्ण मिलान वह मिलान है जो ग्राफ़ के सभी शीर्षों से मेल खाता है। अर्थात्, यदि ग्राफ़ का प्रत्येक शीर्ष मिलान के किनारे पर आपतन (ज्यामिति) हो, तो मिलान पूर्ण होता है। एक मिलान सही है यदि  |E|=|V|/2। प्रत्येक पूर्ण मिलान अधिकतम होता है और इसलिए अधिकतम होता है। कुछ साहित्य में, पूर्ण मिलान शब्द का प्रयोग किया जाता है। उपरोक्त आकृति में, केवल भाग (बी) एक पूर्ण मिलान दिखाता है। एक पूर्ण मिलान न्यूनतम आकार का [[ किनारे का आवरण ]] भी है। इस प्रकार, अधिकतम मिलान का आकार न्यूनतम किनारे के कवर के आकार से बड़ा नहीं है: {{tmath|\nu(G) \le \rho(G)}}. एक ग्राफ़ में केवल तभी पूर्ण मिलान हो सकता है जब ग्राफ़ में सम संख्या में कोने हों।


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


मेल खाते 'M'' को देखते हुए, एक वैकल्पिक पथ एक ऐसा पथ है जो एक बेजोड़ शिखर से शुरू होता है<ref>{{Cite web|url=http://diestel-graph-theory.com/basic.html|title=Preview}}</ref> और जिनके किनारे वैकल्पिक रूप से मिलान के हैं और मिलान के नहीं हैं। संवर्धित पथ एक वैकल्पिक पथ है जो मुक्त (बेजोड़) शीर्षों से शुरू होता है और समाप्त होता है। बर्ज की प्रमेयिका कहती है कि एक मेल खाने वाला 'एम' अधिकतम है अगर और केवल अगर 'एम' के संबंध में कोई संवर्द्धन पथ नहीं है।
मेल खाते 'M'' को देखते हुए, एक वैकल्पिक पथ एक ऐसा पथ है जो एक बेजोड़ शिखर से प्रारंभ  होता है<ref>{{Cite web|url=http://diestel-graph-theory.com/basic.html|title=Preview}}</ref> और जिनके किनारे वैकल्पिक रूप से मिलान के हैं और मिलान के नहीं हैं। संवर्धित पथ एक वैकल्पिक पथ है जो मुक्त (बेजोड़) शीर्षों से प्रारंभ  होता है और समाप्त होता है। बर्ज की प्रमेयिका कहती है कि एक मेल खाने वाला 'एम' अधिकतम है यदि  और केवल यदि  'एम' के संबंध में कोई संवर्द्धन पथ नहीं है।''


एक [[प्रेरित मिलान]] एक मिलान है जो एक [[प्रेरित सबग्राफ]] का किनारा सेट है।<ref>{{citation
एक [[प्रेरित मिलान]] एक मिलान है जो एक [[प्रेरित सबग्राफ]] का किनारा सेट है।<ref>{{citation
Line 40: Line 40:
अलग-अलग शीर्षों के बिना किसी भी ग्राफ़ में, मिलान संख्या और किनारों को कवर करने वाली संख्या का योग शीर्षों की संख्या के बराबर होता है।<ref>{{citation|last=Gallai|first=Tibor|title=Über extreme Punkt- und Kantenmengen|journal=Ann. Univ. Sci. Budapest. Eötvös Sect. Math. |volume=2|pages=133–138|year=1959}}.</ref> यदि कोई पूर्ण मिलान है, तो मिलान संख्या और किनारे का कवर नंबर दोनों हैं {{math|{{!}}''V'' {{!}} / 2}}.
अलग-अलग शीर्षों के बिना किसी भी ग्राफ़ में, मिलान संख्या और किनारों को कवर करने वाली संख्या का योग शीर्षों की संख्या के बराबर होता है।<ref>{{citation|last=Gallai|first=Tibor|title=Über extreme Punkt- und Kantenmengen|journal=Ann. Univ. Sci. Budapest. Eötvös Sect. Math. |volume=2|pages=133–138|year=1959}}.</ref> यदि कोई पूर्ण मिलान है, तो मिलान संख्या और किनारे का कवर नंबर दोनों हैं {{math|{{!}}''V'' {{!}} / 2}}.


अगर {{math|''A''}} और {{math|''B''}} तब दो अधिकतम मिलान हैं {{math|{{!}}''A''{{!}}&nbsp;≤&nbsp;2{{!}}''B''{{!}}}} और {{math|{{!}}''B''{{!}}&nbsp;≤&nbsp;2{{!}}''A''{{!}}}}. इसे देखने के लिए, ध्यान दें कि प्रत्येक किनारे में {{math|''B''&nbsp;\&nbsp;''A''}} अधिकतम दो किनारों के निकट हो सकता है {{math|''A''&nbsp;\&nbsp;''B''}} क्योंकि {{math|''A''}} एक मिलान है; इसके अलावा प्रत्येक किनारे में {{math|''A''&nbsp;\&nbsp;''B''}} में एक किनारे के निकट है {{math|''B''&nbsp;\&nbsp;''A''}} की अधिकतमता से {{math|''B''}}, इस तरह
यदि  {{math|''A''}} और {{math|''B''}} तब दो अधिकतम मिलान हैं {{math|{{!}}''A''{{!}}&nbsp;≤&nbsp;2{{!}}''B''{{!}}}} और {{math|{{!}}''B''{{!}}&nbsp;≤&nbsp;2{{!}}''A''{{!}}}}. इसे देखने के लिए, ध्यान दें कि प्रत्येक किनारे में {{math|''B''&nbsp;\&nbsp;''A''}} अधिकतम दो किनारों के निकट हो सकता है {{math|''A''&nbsp;\&nbsp;''B''}} क्योंकि {{math|''A''}} एक मिलान है; इसके अतिरिक्त  प्रत्येक किनारे में {{math|''A''&nbsp;\&nbsp;''B''}} में एक किनारे के निकट है {{math|''B''&nbsp;\&nbsp;''A''}} की अधिकतमता से {{math|''B''}}, इस तरह


:<math>|A \setminus B| \le 2|B \setminus A |.</math>
:<math>|A \setminus B| \le 2|B \setminus A |.</math>
Line 48: Line 48:
विशेष रूप से, यह दर्शाता है कि कोई भी अधिकतम मिलान अधिकतम मिलान का 2-अनुमान है और न्यूनतम अधिकतम मिलान का 2-अनुमान भी है। यह असमानता तंग है: उदाहरण के लिए, यदि {{math|''G''}} 3 किनारों और 4 शीर्षों वाला पथ है, न्यूनतम अधिकतम मिलान का आकार 1 है और अधिकतम मिलान का आकार 2 है।
विशेष रूप से, यह दर्शाता है कि कोई भी अधिकतम मिलान अधिकतम मिलान का 2-अनुमान है और न्यूनतम अधिकतम मिलान का 2-अनुमान भी है। यह असमानता तंग है: उदाहरण के लिए, यदि {{math|''G''}} 3 किनारों और 4 शीर्षों वाला पथ है, न्यूनतम अधिकतम मिलान का आकार 1 है और अधिकतम मिलान का आकार 2 है।


हसनी मोनफेरेड और मल्लिक द्वारा एक ग्राफ की मिलान संख्या का एक वर्णक्रमीय लक्षण वर्णन निम्नानुसार दिया गया है: मान लीजिए <math>G</math> एक ग्राफ़_ (असतत_गणित) पर रहें <math>n</math> शिखर, और <math>\lambda_1 > \lambda_2 > \ldots > \lambda_k>0</math> होना <math>k</math> विशिष्ट गैर-शून्य [[काल्पनिक संख्या]] जहां <math>2k \leq n</math>. फिर की [[मिलान संख्या]] <math>G</math> है <math>k</math> अगर और केवल अगर (ए) एक वास्तविक [[तिरछा-सममित मैट्रिक्स]] है <math>A</math> ग्राफ के साथ <math>G</math> और [[eigenvalues]] <math>\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_k</math> और <math>n-2k</math> शून्य, और (बी) ग्राफ के साथ सभी वास्तविक तिरछा-सममित आव्यूह <math>G</math> अधिक से अधिक है <math>2k</math> गैर-शून्य ईजेनवेल्यूज़।<ref>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 </ref> ध्यान दें कि एक वास्तविक सममित या तिरछा-सममित मैट्रिक्स का (सरल) ग्राफ <math>A</math> आदेश की <math>n</math> है <math>n</math> के गैर-विकर्ण प्रविष्टियों द्वारा दिए गए कोने और किनारे <math>A</math>.
हसनी मोनफेरेड और मल्लिक द्वारा एक ग्राफ की मिलान संख्या का एक वर्णक्रमीय लक्षण वर्णन निम्नानुसार दिया गया है: मान लीजिए <math>G</math> एक ग्राफ़_ (असतत_गणित) पर रहें <math>n</math> शिखर, और <math>\lambda_1 > \lambda_2 > \ldots > \lambda_k>0</math> होना <math>k</math> विशिष्ट गैर-शून्य [[काल्पनिक संख्या]] जहां <math>2k \leq n</math>. फिर की [[मिलान संख्या]] <math>G</math> है <math>k</math> यदि  और केवल यदि  (ए) एक वास्तविक [[तिरछा-सममित मैट्रिक्स]] है <math>A</math> ग्राफ के साथ <math>G</math> और [[eigenvalues]] <math>\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_k</math> और <math>n-2k</math> शून्य, और (बी) ग्राफ के साथ सभी वास्तविक तिरछा-सममित आव्यूह <math>G</math> अधिक से अधिक है <math>2k</math> गैर-शून्य ईजेनवेल्यूज़।<ref>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 </ref> ध्यान दें कि एक वास्तविक सममित या तिरछा-सममित मैट्रिक्स का (सरल) ग्राफ <math>A</math> आदेश की <math>n</math> है <math>n</math> के गैर-विकर्ण प्रविष्टियों द्वारा दिए गए कोने और किनारे <math>A</math>.


== मिलान बहुपद ==
== मिलान बहुपद ==
Line 69: Line 69:
=== अधिकतम वजन मिलान ===
=== अधिकतम वजन मिलान ===
{{Main|Maximum weight matching}}
{{Main|Maximum weight matching}}
एक भारित ग्राफ़ द्विदलीय ग्राफ़ में, अनुकूलन समस्या एक अधिकतम-भार मिलान खोजने के लिए है; एक न्यूनतम वजन मिलान खोजने के लिए एक दोहरी समस्या है। इस समस्या को अक्सर 'अधिकतम भारित द्विपक्षीय मिलान' या 'असाइनमेंट समस्या' कहा जाता है। [[हंगेरियन एल्गोरिथम]] असाइनमेंट समस्या को हल करता है और यह कॉम्बीनेटरियल ऑप्टिमाइज़ेशन एल्गोरिदम की शुरुआत में से एक था। यह संवर्द्धन पथ एल्गोरिथम में एक संशोधित लघुतम पथ खोज का उपयोग करता है। यदि इस चरण के लिए बेलमैन-फोर्ड एल्गोरिथ्म का उपयोग किया जाता है, तो हंगेरियन एल्गोरिथम का रनिंग टाइम बन जाता है <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
Line 109: Line 109:
=== गिनती की समस्याएं ===
=== गिनती की समस्याएं ===
{{main|Hosoya index}}
{{main|Hosoya index}}
किसी ग्राफ़ में मिलानों की संख्या को ग्राफ़ के [[ कज़ुओ होसोया एक्स ]] के रूप में जाना जाता है। द्विदलीय रेखांकन के लिए भी, इस मात्रा की गणना करने के लिए यह तीव्र-पी-पूर्ण|#पी-पूर्ण है।<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á
| last1        = Bezáková
| first1      = Ivona
| first1      = Ivona
Line 128: Line 128:
| citeseerx= 10.1.1.80.687
| citeseerx= 10.1.1.80.687
| s2cid = 755231
| s2cid = 755231
}}</ref> [[पीटर कास्टली द्वारा]] के एक उल्लेखनीय प्रमेय में कहा गया है कि [[एफकेटी एल्गोरिदम]] के माध्यम से एक प्लेनर ग्राफ में सही मिलान की संख्या बहुपद समय में सटीक रूप से गणना की जा सकती है।
}}</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
Line 146: Line 146:
=== सभी अधिकतम मिलान करने योग्य किनारों का पता लगाना ===
=== सभी अधिकतम मिलान करने योग्य किनारों का पता लगाना ===
{{Main|Maximally matchable edge}}
{{Main|Maximally matchable edge}}
मिलान सिद्धांत में बुनियादी समस्याओं में से एक दिए गए ग्राफ़ में सभी किनारों को खोजना है जिन्हें ग्राफ़ में अधिकतम मिलान तक बढ़ाया जा सकता है (ऐसे किनारों को अधिकतम मिलान करने योग्य किनारे या अनुमत किनारे कहा जाता है)। इस समस्या के एल्गोरिदम में शामिल हैं:
मिलान सिद्धांत में मौलिक  समस्याओं में से एक दिए गए ग्राफ़ में सभी किनारों को खोजना है जिन्हें ग्राफ़ में अधिकतम मिलान तक बढ़ाया जा सकता है (ऐसे किनारों को अधिकतम मिलान करने योग्य किनारे या अनुमत किनारे कहा जाता है)। इस समस्या के एल्गोरिदम में सम्मलित  हैं:


* सामान्य रेखांकन के लिए, समय में एक नियतात्मक एल्गोरिथ्म <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
Line 181: Line 181:


=== ऑनलाइन द्विपक्षीय मिलान ===
=== ऑनलाइन द्विपक्षीय मिलान ===
मिलान के लिए एक [[ ऑनलाइन एल्गोरिदम ]] विकसित करने की समस्या पर सबसे पहले 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>




Line 195: Line 195:
* [[सुगंध]] की एक केकुले संरचना में इसके [[कंकाल सूत्र]] का सही मिलान होता है, जो [[रासायनिक संरचना]] में दोहरे बंधनों के स्थानों को दर्शाता है। इन संरचनाओं का नाम फ्रेडरिक अगस्त केकुले वॉन स्ट्रैडोनिट्ज़ के नाम पर रखा गया है, जिन्होंने दिखाया कि [[बेंजीन]] (ग्राफ़ सैद्धांतिक शब्दों में, एक 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 ग्रेजुएशन प्रॉब्लम] ग्रेजुएशन के लिए दी गई आवश्यकताओं में से कक्षाओं के न्यूनतम सेट को चुनने के बारे में है।
* [[परिवहन सिद्धांत (गणित)]] में उप-समस्या के रूप में द्विदलीय मिलान शामिल है।
* [[परिवहन सिद्धांत (गणित)]] में उप-समस्या के रूप में द्विदलीय मिलान सम्मलित  है।
* [[सबग्राफ समरूपता समस्या]] समस्या में उप-समस्या के रूप में द्विदलीय मिलान शामिल है।
* [[सबग्राफ समरूपता समस्या]] समस्या में उप-समस्या के रूप में द्विदलीय मिलान सम्मलित  है।


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


Revision as of 12:13, 5 May 2023

For comparisons of two graphs, see Graph matching.

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

Covering/packing-problem pairs
Covering problems Packing problems
Minimum set cover Maximum set packing
Minimum edge cover Maximum matching
Minimum vertex cover Maximum independent set
Bin covering Bin packing
Polygon covering Rectangle packing

परिभाषाएँ

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

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

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

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

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

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

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


गुण

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

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

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

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

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

मिलान बहुपद

Main article: Matching polynomial

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

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

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

एल्गोरिदम और कम्प्यूटेशनल जटिलता

अधिकतम-कार्डिनैलिटी मिलान

Main article: Maximum cardinality matching

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

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

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

Main article: Maximum weight matching

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

अधिकतम मिलान

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

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


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

Main article: Hosoya index

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

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


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

Main article: Maximally matchable edge

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

  • सामान्य रेखांकन के लिए, समय में एक नियतात्मक एल्गोरिथ्म और समय में एक यादृच्छिक एल्गोरिदम .[15][16]
  • द्विदलीय रेखांकन के लिए, यदि एक एकल अधिकतम मिलान पाया जाता है, तो नियतात्मक एल्गोरिथ्म समय में चलता है .[17]


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

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


लक्षण

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

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

अनुप्रयोग

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

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

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

यह भी देखें

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

संदर्भ

  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
  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 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. 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


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=मिलान_(ग्राफ_सिद्धांत)&oldid=273561’