अधिकतम कार्डिनैलिटी मिलान: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Graph theory problem: find a matching containing the most edges}} ग्राफ़ सिद्धांत में अधिकतम कार्ड...")
 
No edit summary
Line 1: Line 1:
{{short description|Graph theory problem: find a matching containing the most edges}}
{{short description|Graph theory problem: find a matching containing the most edges}}


ग्राफ़ सिद्धांत में अधिकतम कार्डिनैलिटी मिलान एक मूलभूत समस्या है।<ref name="Wes01">{{citation|last=West|first=Douglas Brent|title=Introduction to Graph Theory|year=1999|at=Chapter 3|edition=2nd|publisher=Prentice Hall|isbn=0-13-014400-2}}</ref>
ग्राफ़ सिद्धांत में अधिकतम कार्डिनैलिटी मिलान मूलभूत समस्या है।<ref name="Wes01">{{citation|last=West|first=Douglas Brent|title=Introduction to Graph Theory|year=1999|at=Chapter 3|edition=2nd|publisher=Prentice Hall|isbn=0-13-014400-2}}</ref>
हमें एक ग्राफ़ दिया गया है (ग्राफ़ सिद्धांत) {{mvar|G}}, और लक्ष्य एक मिलान (ग्राफ़ सिद्धांत) ढूंढना है जिसमें यथासंभव अधिक किनारे हों; अर्थात्, किनारों का अधिकतम [[प्रमुखता]] उपसमुच्चय इस प्रकार है कि प्रत्येक शीर्ष (ग्राफ़ सिद्धांत) उपसमुच्चय के अधिकतम एक किनारे से सटा हुआ हो। चूँकि प्रत्येक किनारा बिल्कुल दो शीर्षों को कवर करेगा, यह समस्या एक ऐसे मिलान को खोजने के कार्य के बराबर है जो यथासंभव अधिक से अधिक शीर्षों को कवर करता है।
हमें ग्राफ़ दिया गया है (ग्राफ़ सिद्धांत) {{mvar|G}}, और लक्ष्य मिलान (ग्राफ़ सिद्धांत) ढूंढना है जिसमें यथासंभव अधिक किनारे हों; अर्थात्, किनारों का अधिकतम [[प्रमुखता]] उपसमुच्चय इस प्रकार है कि प्रत्येक शीर्ष (ग्राफ़ सिद्धांत) उपसमुच्चय के अधिकतम किनारे से सटा हुआ हो। चूँकि प्रत्येक किनारा बिल्कुल दो शीर्षों को कवर करेगा, यह समस्या ऐसे मिलान को खोजने के कार्य के बराबर है जो यथासंभव अधिक से अधिक शीर्षों को कवर करता है।


अधिकतम कार्डिनैलिटी मिलान समस्या का एक महत्वपूर्ण [[विशेष मामला]] कब है {{mvar|G}} एक [[द्विदलीय ग्राफ]] है, जिसके शीर्ष {{mvar|V}} को बाएँ शीर्षों के बीच विभाजित किया गया है {{mvar|X}} और दाएं कोने में {{mvar|Y}}, और किनारों में {{mvar|E}} हमेशा बाएँ शीर्ष को दाएँ शीर्ष से जोड़ें। इस मामले में, समस्या को सामान्य मामले की तुलना में सरल एल्गोरिदम के साथ कुशलतापूर्वक हल किया जा सकता है।
अधिकतम कार्डिनैलिटी मिलान समस्या का महत्वपूर्ण [[विशेष मामला]] कब है {{mvar|G}} [[द्विदलीय ग्राफ]] है, जिसके शीर्ष {{mvar|V}} को बाएँ शीर्षों के बीच विभाजित किया गया है {{mvar|X}} और दाएं कोने में {{mvar|Y}}, और किनारों में {{mvar|E}} हमेशा बाएँ शीर्ष को दाएँ शीर्ष से जोड़ें। इस मामले में, समस्या को सामान्य मामले की तुलना में सरल एल्गोरिदम के साथ कुशलतापूर्वक हल किया जा सकता है।


== द्विदलीय ग्राफ़ के लिए एल्गोरिदम ==
== द्विदलीय ग्राफ़ के लिए एल्गोरिदम ==


=== प्रवाह-आधारित एल्गोरिदम ===
=== प्रवाह-आधारित एल्गोरिदम ===
अधिकतम कार्डिनैलिटी मिलान की गणना करने का सबसे सरल तरीका फोर्ड-फुलकर्सन एल्गोरिदम का पालन करना है। यह एल्गोरिदम [[अधिकतम प्रवाह समस्या]] की अधिक सामान्य समस्या को हल करता है। एक द्विदलीय ग्राफ {{math|(''X'' + ''Y'', ''E'')}} को निम्नानुसार [[प्रवाह नेटवर्क]] में परिवर्तित किया जा सकता है।
अधिकतम कार्डिनैलिटी मिलान की गणना करने का सबसे सरल तरीका फोर्ड-फुलकर्सन एल्गोरिदम का पालन करना है। यह एल्गोरिदम [[अधिकतम प्रवाह समस्या]] की अधिक सामान्य समस्या को हल करता है। द्विदलीय ग्राफ {{math|(''X'' + ''Y'', ''E'')}} को निम्नानुसार [[प्रवाह नेटवर्क]] में परिवर्तित किया जा सकता है।


* एक स्रोत शीर्ष जोड़ें {{mvar|s}}; से एक किनारा जोड़ें {{mvar|s}} प्रत्येक शीर्ष पर {{mvar|X}}.
* एक स्रोत शीर्ष जोड़ें {{mvar|s}}; से किनारा जोड़ें {{mvar|s}} प्रत्येक शीर्ष पर {{mvar|X}}.
* एक सिंक शीर्ष जोड़ें {{mvar|t}}; प्रत्येक शीर्ष से एक किनारा जोड़ें {{mvar|Y}} को {{mvar|t}}.
* एक सिंक शीर्ष जोड़ें {{mvar|t}}; प्रत्येक शीर्ष से किनारा जोड़ें {{mvar|Y}} को {{mvar|t}}.
* प्रत्येक किनारे पर 1 की क्षमता निर्दिष्ट करें।
* प्रत्येक किनारे पर 1 की क्षमता निर्दिष्ट करें।


चूंकि नेटवर्क में प्रत्येक किनारे की अभिन्न क्षमता होती है, इसलिए एक अधिकतम प्रवाह मौजूद होता है जहां सभी प्रवाह पूर्णांक होते हैं; ये पूर्णांक या तो 0 या 1 होने चाहिए क्योंकि सभी क्षमताएं 1 हैं। प्रत्येक अभिन्न प्रवाह एक मिलान को परिभाषित करता है जिसमें एक किनारा मिलान में होता है यदि और केवल यदि इसका प्रवाह 1 है। यह एक मिलान है क्योंकि:
चूंकि नेटवर्क में प्रत्येक किनारे की अभिन्न क्षमता होती है, इसलिए अधिकतम प्रवाह मौजूद होता है जहां सभी प्रवाह पूर्णांक होते हैं; ये पूर्णांक या तो 0 या 1 होने चाहिए क्योंकि सभी क्षमताएं 1 हैं। प्रत्येक अभिन्न प्रवाह मिलान को परिभाषित करता है जिसमें किनारा मिलान में होता है यदि और केवल यदि इसका प्रवाह 1 है। यह मिलान है क्योंकि:


* प्रत्येक शीर्ष पर आने वाला प्रवाह {{mvar|X}} अधिकतम 1 है, इसलिए आउटगोइंग प्रवाह भी अधिकतम 1 है, इसलिए प्रत्येक शीर्ष के निकट अधिकतम एक किनारा है {{mvar|X}} मौजूद है।
* प्रत्येक शीर्ष पर आने वाला प्रवाह {{mvar|X}} अधिकतम 1 है, इसलिए आउटगोइंग प्रवाह भी अधिकतम 1 है, इसलिए प्रत्येक शीर्ष के निकट अधिकतम किनारा है {{mvar|X}} मौजूद है।
* प्रत्येक शीर्ष से निवर्तमान प्रवाह {{mvar|Y}} अधिकतम 1 है, इसलिए आने वाला प्रवाह भी अधिकतम 1 है, इसलिए अधिकतम प्रत्येक शीर्ष के निकट एक किनारा है {{mvar|Y}} मौजूद है।
* प्रत्येक शीर्ष से निवर्तमान प्रवाह {{mvar|Y}} अधिकतम 1 है, इसलिए आने वाला प्रवाह भी अधिकतम 1 है, इसलिए अधिकतम प्रत्येक शीर्ष के निकट किनारा है {{mvar|Y}} मौजूद है।


फोर्ड-फ़ल्कर्सन एल्गोरिदम बार-बार कुछ से एक संवर्द्धन पथ ढूंढकर आगे बढ़ता है {{math|''x'' ∈ ''X''}} कुछ करने के लिए {{math|''y'' ∈ {{mvar|Y}}}} और मिलान को अद्यतन कर रहा हूँ {{mvar|M}} उस पथ के सममित अंतर को साथ लेकर {{mvar|M}} (यह मानते हुए कि ऐसा पथ मौजूद है)। जैसा कि प्रत्येक पथ में पाया जा सकता है {{math|[[Big O notation|''O'']](''E'')}} समय, चलने का समय है {{math|''O''(''VE'')}}, और अधिकतम मिलान में किनारों का समावेश होता है {{mvar|E}} जिससे प्रवाह होता है {{mvar|X}} को {{mvar|Y}}.
फोर्ड-फ़ल्कर्सन एल्गोरिदम बार-बार कुछ से संवर्द्धन पथ ढूंढकर आगे बढ़ता है {{math|''x'' ∈ ''X''}} कुछ करने के लिए {{math|''y'' ∈ {{mvar|Y}}}} और मिलान को अद्यतन कर रहा हूँ {{mvar|M}} उस पथ के सममित अंतर को साथ लेकर {{mvar|M}} (यह मानते हुए कि ऐसा पथ मौजूद है)। जैसा कि प्रत्येक पथ में पाया जा सकता है {{math|[[Big O notation|''O'']](''E'')}} समय, चलने का समय है {{math|''O''(''VE'')}}, और अधिकतम मिलान में किनारों का समावेश होता है {{mvar|E}} जिससे प्रवाह होता है {{mvar|X}} को {{mvar|Y}}.


=== उन्नत एल्गोरिदम ===
=== उन्नत एल्गोरिदम ===
इस एल्गोरिदम में सुधार अधिक विस्तृत हॉपक्रॉफ्ट-कार्प एल्गोरिदम द्वारा दिया गया है, जो एक साथ कई संवर्द्धन पथों की खोज करता है। यह एल्गोरिदम चलता है <math>O(\sqrt{V}E)</math> समय।
इस एल्गोरिदम में सुधार अधिक विस्तृत हॉपक्रॉफ्ट-कार्प एल्गोरिदम द्वारा दिया गया है, जो साथ कई संवर्द्धन पथों की खोज करता है। यह एल्गोरिदम चलता है <math>O(\sqrt{V}E)</math> समय।


चंद्रन और होचबाम का एल्गोरिदम<ref name="Chandran" />द्विदलीय ग्राफ़ समय के अनुसार चलते हैं जो अधिकतम मिलान के आकार पर निर्भर करता है {{mvar|k}}, जिसके लिए {{math|{{abs|''X''}} < {{abs|''Y''}}}} है
चंद्रन और होचबाम का एल्गोरिदम<ref name="Chandran" />द्विदलीय ग्राफ़ समय के अनुसार चलते हैं जो अधिकतम मिलान के आकार पर निर्भर करता है {{mvar|k}}, जिसके लिए {{math|{{abs|''X''}} < {{abs|''Y''}}}} है
Line 34: Line 34:
== मनमाना ग्राफ़ के लिए एल्गोरिदम ==
== मनमाना ग्राफ़ के लिए एल्गोरिदम ==


[[खिलना एल्गोरिथ्म]] सामान्य (जरूरी नहीं कि द्विदलीय) ग्राफ़ में अधिकतम-कार्डिनैलिटी मिलान पाता है। यह समय के अनुसार चलता है <math>O(|V|^2 \cdot |E|)</math>. का बेहतर प्रदर्शन {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} सामान्य ग्राफ़ के लिए, द्विदलीय ग्राफ़ पर हॉपक्रॉफ्ट-कार्प एल्गोरिदम के प्रदर्शन से मेल खाते हुए, मिकाली और वज़ीरानी के बहुत अधिक जटिल एल्गोरिदम के साथ प्राप्त किया जा सकता है।<ref>{{citation|last1=Micali|first1=S.|title=[[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]]|pages=17–27|year=1980|contribution=An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs|doi=10.1109/SFCS.1980.12|last2=Vazirani|first2=V. V.|s2cid=27467816|author1-link=Silvio Micali|author2-link=Vijay Vazirani}}.</ref> वही सीमा [[नॉर्बर्ट ब्लम (कंप्यूटर वैज्ञानिक)]] द्वारा एक एल्गोरिदम द्वारा हासिल की गई थी (:de:Norbert Blum)<ref>{{Cite journal|last=Blum|first=Norbert|date=1990|editor-last=Paterson|editor-first=Michael S.|title=सामान्य ग्राफ़ में अधिकतम मिलान के लिए एक नया दृष्टिकोण|url=https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf|journal=Automata, Languages and Programming|series=Lecture Notes in Computer Science|volume=443|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=586–597|doi=10.1007/BFb0032060|isbn=978-3-540-47159-2}}</ref> और हेरोल्ड एन. गैबो और [[रॉबर्ट टार्जन]] द्वारा एक एल्गोरिदम।<ref>{{Cite journal|first1=Harold N|last1=Gabow|author1-link=Harold N. Gabow|first2=Robert E|last2=Tarjan|date=1991-10-01|title=सामान्य ग्राफ़ मिलान समस्याओं के लिए तेज़ स्केलिंग एल्गोरिदम|url=https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf|journal=Journal of the ACM|volume=38|issue=4|pages=815–853|language=EN|doi=10.1145/115234.115366|s2cid=18350108}}</ref>
[[खिलना एल्गोरिथ्म]] सामान्य (जरूरी नहीं कि द्विदलीय) ग्राफ़ में अधिकतम-कार्डिनैलिटी मिलान पाता है। यह समय के अनुसार चलता है <math>O(|V|^2 \cdot |E|)</math>. का बेहतर प्रदर्शन {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} सामान्य ग्राफ़ के लिए, द्विदलीय ग्राफ़ पर हॉपक्रॉफ्ट-कार्प एल्गोरिदम के प्रदर्शन से मेल खाते हुए, मिकाली और वज़ीरानी के बहुत अधिक जटिल एल्गोरिदम के साथ प्राप्त किया जा सकता है।<ref>{{citation|last1=Micali|first1=S.|title=[[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]]|pages=17–27|year=1980|contribution=An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs|doi=10.1109/SFCS.1980.12|last2=Vazirani|first2=V. V.|s2cid=27467816|author1-link=Silvio Micali|author2-link=Vijay Vazirani}}.</ref> वही सीमा [[नॉर्बर्ट ब्लम (कंप्यूटर वैज्ञानिक)]] द्वारा एल्गोरिदम द्वारा हासिल की गई थी (:de:Norbert Blum)<ref>{{Cite journal|last=Blum|first=Norbert|date=1990|editor-last=Paterson|editor-first=Michael S.|title=सामान्य ग्राफ़ में अधिकतम मिलान के लिए एक नया दृष्टिकोण|url=https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf|journal=Automata, Languages and Programming|series=Lecture Notes in Computer Science|volume=443|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=586–597|doi=10.1007/BFb0032060|isbn=978-3-540-47159-2}}</ref> और हेरोल्ड एन. गैबो और [[रॉबर्ट टार्जन]] द्वारा एल्गोरिदम।<ref>{{Cite journal|first1=Harold N|last1=Gabow|author1-link=Harold N. Gabow|first2=Robert E|last2=Tarjan|date=1991-10-01|title=सामान्य ग्राफ़ मिलान समस्याओं के लिए तेज़ स्केलिंग एल्गोरिदम|url=https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf|journal=Journal of the ACM|volume=38|issue=4|pages=815–853|language=EN|doi=10.1145/115234.115366|s2cid=18350108}}</ref>
एक वैकल्पिक दृष्टिकोण [[यादृच्छिक एल्गोरिदम]] का उपयोग करता है और तेज़ [[मैट्रिक्स गुणन]] एल्गोरिदम पर आधारित है। यह जटिलता वाले सामान्य ग्राफ़ के लिए एक यादृच्छिक एल्गोरिदम देता है <math>O(V^{2.376})</math>.<ref name="Mucha">{{citation|last1=Mucha|first1=M.|title=[[Symposium on Foundations of Computer Science|Proc. 45th IEEE Symp. Foundations of Computer Science]]|pages=248–255|year=2004|contribution=Maximum Matchings via Gaussian Elimination|contribution-url=http://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf|last2=Sankowski|first2=P.}}</ref> यह पर्याप्त [[सघन ग्राफ]]़ के लिए सिद्धांत रूप में बेहतर है, लेकिन व्यवहार में एल्गोरिथ्म धीमा है।<ref name="Chandran">{{citation|last1=Chandran|first1=Bala G.|title=Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm|year=2011|arxiv=1105.1569|bibcode=2011arXiv1105.1569C|quote=the theoretically efficient algorithms listed above tend to perform poorly in practice|last2=Hochbaum|first2=Dorit S.|author2-link=Dorit S. Hochbaum}}.</ref>
एक वैकल्पिक दृष्टिकोण [[यादृच्छिक एल्गोरिदम]] का उपयोग करता है और तेज़ [[मैट्रिक्स गुणन]] एल्गोरिदम पर आधारित है। यह जटिलता वाले सामान्य ग्राफ़ के लिए यादृच्छिक एल्गोरिदम देता है <math>O(V^{2.376})</math>.<ref name="Mucha">{{citation|last1=Mucha|first1=M.|title=[[Symposium on Foundations of Computer Science|Proc. 45th IEEE Symp. Foundations of Computer Science]]|pages=248–255|year=2004|contribution=Maximum Matchings via Gaussian Elimination|contribution-url=http://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf|last2=Sankowski|first2=P.}}</ref> यह पर्याप्त [[सघन ग्राफ]]़ के लिए सिद्धांत रूप में बेहतर है, लेकिन व्यवहार में एल्गोरिथ्म धीमा है।<ref name="Chandran">{{citation|last1=Chandran|first1=Bala G.|title=Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm|year=2011|arxiv=1105.1569|bibcode=2011arXiv1105.1569C|quote=the theoretically efficient algorithms listed above tend to perform poorly in practice|last2=Hochbaum|first2=Dorit S.|author2-link=Dorit S. Hochbaum}}.</ref>
कार्य के लिए अन्य एल्गोरिदम की समीक्षा डुआन और पेटी द्वारा की जाती है<ref>{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=अधिकतम वजन मिलान के लिए रैखिक-समय अनुमान|url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf|journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641}}</ref> (तालिका I देखें)। सन्निकटन एल्गोरिदम के संदर्भ में, वे यह भी बताते हैं कि ब्लॉसम एल्गोरिदम और मिकाली और वज़ीरानी के एल्गोरिदम को किसी भी निश्चित त्रुटि सीमा के लिए रैखिक समय में चलने वाले सन्निकटन एल्गोरिदम के रूप में देखा जा सकता है।
कार्य के लिए अन्य एल्गोरिदम की समीक्षा डुआन और पेटी द्वारा की जाती है<ref>{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=अधिकतम वजन मिलान के लिए रैखिक-समय अनुमान|url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf|journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641}}</ref> (तालिका I देखें)। सन्निकटन एल्गोरिदम के संदर्भ में, वे यह भी बताते हैं कि ब्लॉसम एल्गोरिदम और मिकाली और वज़ीरानी के एल्गोरिदम को किसी भी निश्चित त्रुटि सीमा के लिए रैखिक समय में चलने वाले सन्निकटन एल्गोरिदम के रूप में देखा जा सकता है।


Line 41: Line 41:


* अधिकतम-कार्डिनैलिटी मिलान ढूंढकर, यह तय करना संभव है कि क्या कोई पूर्ण मिलान मौजूद है।
* अधिकतम-कार्डिनैलिटी मिलान ढूंढकर, यह तय करना संभव है कि क्या कोई पूर्ण मिलान मौजूद है।
* [[भारित ग्राफ]]़ में अधिकतम वजन के साथ मिलान खोजने की समस्या को [[अधिकतम वजन मिलान]] कहा जाता है, और द्विदलीय ग्राफ़ पर इसके प्रतिबंध को [[असाइनमेंट समस्या]] कहा जाता है। यदि प्रत्येक शीर्ष का एक साथ कई शीर्षों से मिलान किया जा सकता है, तो यह एक [[सामान्यीकृत असाइनमेंट समस्या]] है।
* [[भारित ग्राफ]]़ में अधिकतम वजन के साथ मिलान खोजने की समस्या को [[अधिकतम वजन मिलान]] कहा जाता है, और द्विदलीय ग्राफ़ पर इसके प्रतिबंध को [[असाइनमेंट समस्या]] कहा जाता है। यदि प्रत्येक शीर्ष का साथ कई शीर्षों से मिलान किया जा सकता है, तो यह [[सामान्यीकृत असाइनमेंट समस्या]] है।
* [[प्राथमिकता मिलान]] एक विशेष अधिकतम-कार्डिनैलिटी मिलान है जिसमें प्राथमिकता वाले शीर्षों का मिलान पहले किया जाता है।
* [[प्राथमिकता मिलान]] विशेष अधिकतम-कार्डिनैलिटी मिलान है जिसमें प्राथमिकता वाले शीर्षों का मिलान पहले किया जाता है।
* हाइपरग्राफ में अधिकतम-कार्डिनैलिटी मिलान खोजने की समस्या 3-समान हाइपरग्राफ के लिए भी एनपी-पूर्ण है।<ref>{{Citation|last=Karp|first=Richard M.|title=Reducibility among Combinatorial Problems|date=1972|work=Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department|pages=85–103|editor-last=Miller|editor-first=Raymond E.|series=The IBM Research Symposia Series|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-1-4684-2001-2_9|isbn=978-1-4684-2001-2|editor2-last=Thatcher|editor2-first=James W.|editor3-last=Bohlinger|editor3-first=Jean D.}}</ref>
* हाइपरग्राफ में अधिकतम-कार्डिनैलिटी मिलान खोजने की समस्या 3-समान हाइपरग्राफ के लिए भी एनपी-पूर्ण है।<ref>{{Citation|last=Karp|first=Richard M.|title=Reducibility among Combinatorial Problems|date=1972|work=Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department|pages=85–103|editor-last=Miller|editor-first=Raymond E.|series=The IBM Research Symposia Series|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-1-4684-2001-2_9|isbn=978-1-4684-2001-2|editor2-last=Thatcher|editor2-first=James W.|editor3-last=Bohlinger|editor3-first=Jean D.}}</ref>


Revision as of 17:09, 3 July 2023

ग्राफ़ सिद्धांत में अधिकतम कार्डिनैलिटी मिलान मूलभूत समस्या है।[1] हमें ग्राफ़ दिया गया है (ग्राफ़ सिद्धांत) G, और लक्ष्य मिलान (ग्राफ़ सिद्धांत) ढूंढना है जिसमें यथासंभव अधिक किनारे हों; अर्थात्, किनारों का अधिकतम प्रमुखता उपसमुच्चय इस प्रकार है कि प्रत्येक शीर्ष (ग्राफ़ सिद्धांत) उपसमुच्चय के अधिकतम किनारे से सटा हुआ हो। चूँकि प्रत्येक किनारा बिल्कुल दो शीर्षों को कवर करेगा, यह समस्या ऐसे मिलान को खोजने के कार्य के बराबर है जो यथासंभव अधिक से अधिक शीर्षों को कवर करता है।

अधिकतम कार्डिनैलिटी मिलान समस्या का महत्वपूर्ण विशेष मामला कब है G द्विदलीय ग्राफ है, जिसके शीर्ष V को बाएँ शीर्षों के बीच विभाजित किया गया है X और दाएं कोने में Y, और किनारों में E हमेशा बाएँ शीर्ष को दाएँ शीर्ष से जोड़ें। इस मामले में, समस्या को सामान्य मामले की तुलना में सरल एल्गोरिदम के साथ कुशलतापूर्वक हल किया जा सकता है।

द्विदलीय ग्राफ़ के लिए एल्गोरिदम

प्रवाह-आधारित एल्गोरिदम

अधिकतम कार्डिनैलिटी मिलान की गणना करने का सबसे सरल तरीका फोर्ड-फुलकर्सन एल्गोरिदम का पालन करना है। यह एल्गोरिदम अधिकतम प्रवाह समस्या की अधिक सामान्य समस्या को हल करता है। द्विदलीय ग्राफ (X + Y, E) को निम्नानुसार प्रवाह नेटवर्क में परिवर्तित किया जा सकता है।

  • एक स्रोत शीर्ष जोड़ें s; से किनारा जोड़ें s प्रत्येक शीर्ष पर X.
  • एक सिंक शीर्ष जोड़ें t; प्रत्येक शीर्ष से किनारा जोड़ें Y को t.
  • प्रत्येक किनारे पर 1 की क्षमता निर्दिष्ट करें।

चूंकि नेटवर्क में प्रत्येक किनारे की अभिन्न क्षमता होती है, इसलिए अधिकतम प्रवाह मौजूद होता है जहां सभी प्रवाह पूर्णांक होते हैं; ये पूर्णांक या तो 0 या 1 होने चाहिए क्योंकि सभी क्षमताएं 1 हैं। प्रत्येक अभिन्न प्रवाह मिलान को परिभाषित करता है जिसमें किनारा मिलान में होता है यदि और केवल यदि इसका प्रवाह 1 है। यह मिलान है क्योंकि:

  • प्रत्येक शीर्ष पर आने वाला प्रवाह X अधिकतम 1 है, इसलिए आउटगोइंग प्रवाह भी अधिकतम 1 है, इसलिए प्रत्येक शीर्ष के निकट अधिकतम किनारा है X मौजूद है।
  • प्रत्येक शीर्ष से निवर्तमान प्रवाह Y अधिकतम 1 है, इसलिए आने वाला प्रवाह भी अधिकतम 1 है, इसलिए अधिकतम प्रत्येक शीर्ष के निकट किनारा है Y मौजूद है।

फोर्ड-फ़ल्कर्सन एल्गोरिदम बार-बार कुछ से संवर्द्धन पथ ढूंढकर आगे बढ़ता है x ∈ X कुछ करने के लिए y ∈ Y और मिलान को अद्यतन कर रहा हूँ M उस पथ के सममित अंतर को साथ लेकर M (यह मानते हुए कि ऐसा पथ मौजूद है)। जैसा कि प्रत्येक पथ में पाया जा सकता है O(E) समय, चलने का समय है O(VE), और अधिकतम मिलान में किनारों का समावेश होता है E जिससे प्रवाह होता है X को Y.

उन्नत एल्गोरिदम

इस एल्गोरिदम में सुधार अधिक विस्तृत हॉपक्रॉफ्ट-कार्प एल्गोरिदम द्वारा दिया गया है, जो साथ कई संवर्द्धन पथों की खोज करता है। यह एल्गोरिदम चलता है समय।

चंद्रन और होचबाम का एल्गोरिदम[2]द्विदलीय ग्राफ़ समय के अनुसार चलते हैं जो अधिकतम मिलान के आकार पर निर्भर करता है k, जिसके लिए |X| < |Y| है

आकार के शब्दों पर बूलियन ऑपरेशन का उपयोग करना जटिलता को और बेहतर बनाया गया है[2]: विशेष प्रकार के द्विदलीय ग्राफ़ के लिए अधिक कुशल एल्गोरिदम मौजूद हैं:

  • विरल ग्राफ़ द्विदलीय ग्राफ़ के लिए, अधिकतम मिलान समस्या को हल किया जा सकता है विद्युत प्रवाह पर आधारित मैड्री के एल्गोरिदम के साथ।[3] * समतलीय ग्राफ़ द्विदलीय ग्राफ़ के लिए, समस्या को समय पर हल किया जा सकता है O(n log3 n) कहाँ n एकाधिक स्रोतों और सिंक के साथ समस्या को अधिकतम प्रवाह तक कम करके, शीर्षों की संख्या है।[4]


मनमाना ग्राफ़ के लिए एल्गोरिदम

खिलना एल्गोरिथ्म सामान्य (जरूरी नहीं कि द्विदलीय) ग्राफ़ में अधिकतम-कार्डिनैलिटी मिलान पाता है। यह समय के अनुसार चलता है . का बेहतर प्रदर्शन O(√VE) सामान्य ग्राफ़ के लिए, द्विदलीय ग्राफ़ पर हॉपक्रॉफ्ट-कार्प एल्गोरिदम के प्रदर्शन से मेल खाते हुए, मिकाली और वज़ीरानी के बहुत अधिक जटिल एल्गोरिदम के साथ प्राप्त किया जा सकता है।[5] वही सीमा नॉर्बर्ट ब्लम (कंप्यूटर वैज्ञानिक) द्वारा एल्गोरिदम द्वारा हासिल की गई थी (:de:Norbert Blum)[6] और हेरोल्ड एन. गैबो और रॉबर्ट टार्जन द्वारा एल्गोरिदम।[7] एक वैकल्पिक दृष्टिकोण यादृच्छिक एल्गोरिदम का उपयोग करता है और तेज़ मैट्रिक्स गुणन एल्गोरिदम पर आधारित है। यह जटिलता वाले सामान्य ग्राफ़ के लिए यादृच्छिक एल्गोरिदम देता है .[8] यह पर्याप्त सघन ग्राफ़ के लिए सिद्धांत रूप में बेहतर है, लेकिन व्यवहार में एल्गोरिथ्म धीमा है।[2] कार्य के लिए अन्य एल्गोरिदम की समीक्षा डुआन और पेटी द्वारा की जाती है[9] (तालिका I देखें)। सन्निकटन एल्गोरिदम के संदर्भ में, वे यह भी बताते हैं कि ब्लॉसम एल्गोरिदम और मिकाली और वज़ीरानी के एल्गोरिदम को किसी भी निश्चित त्रुटि सीमा के लिए रैखिक समय में चलने वाले सन्निकटन एल्गोरिदम के रूप में देखा जा सकता है।

अनुप्रयोग और सामान्यीकरण

  • अधिकतम-कार्डिनैलिटी मिलान ढूंढकर, यह तय करना संभव है कि क्या कोई पूर्ण मिलान मौजूद है।
  • भारित ग्राफ़ में अधिकतम वजन के साथ मिलान खोजने की समस्या को अधिकतम वजन मिलान कहा जाता है, और द्विदलीय ग्राफ़ पर इसके प्रतिबंध को असाइनमेंट समस्या कहा जाता है। यदि प्रत्येक शीर्ष का साथ कई शीर्षों से मिलान किया जा सकता है, तो यह सामान्यीकृत असाइनमेंट समस्या है।
  • प्राथमिकता मिलान विशेष अधिकतम-कार्डिनैलिटी मिलान है जिसमें प्राथमिकता वाले शीर्षों का मिलान पहले किया जाता है।
  • हाइपरग्राफ में अधिकतम-कार्डिनैलिटी मिलान खोजने की समस्या 3-समान हाइपरग्राफ के लिए भी एनपी-पूर्ण है।[10]


संदर्भ

  1. ↑ West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
  2. ↑ 2.0 2.1 2.2 Chandran, Bala G.; Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, arXiv:1105.1569, Bibcode:2011arXiv1105.1569C, the theoretically efficient algorithms listed above tend to perform poorly in practice.
  3. ↑ Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262, arXiv:1307.2205, Bibcode:2013arXiv1307.2205M
  4. ↑ Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing, 46 (4): 1280–1303, arXiv:1105.2228, doi:10.1137/15M1042929, MR 3681377, S2CID 207071917
  5. ↑ Micali, S.; Vazirani, V. V. (1980), "An algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12, S2CID 27467816.
  6. ↑ Blum, Norbert (1990). Paterson, Michael S. (ed.). "सामान्य ग्राफ़ में अधिकतम मिलान के लिए एक नया दृष्टिकोण" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 443: 586–597. doi:10.1007/BFb0032060. ISBN 978-3-540-47159-2.
  7. ↑ Gabow, Harold N; Tarjan, Robert E (1991-10-01). "सामान्य ग्राफ़ मिलान समस्याओं के लिए तेज़ स्केलिंग एल्गोरिदम" (PDF). Journal of the ACM (in English). 38 (4): 815–853. doi:10.1145/115234.115366. S2CID 18350108.
  8. ↑ Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 248–255
  9. ↑ Duan, Ran; Pettie, Seth (2014-01-01). "अधिकतम वजन मिलान के लिए रैखिक-समय अनुमान" (PDF). Journal of the ACM (in English). 61: 1–23. doi:10.1145/2529989. S2CID 207208641.
  10. ↑ Karp, Richard M. (1972), Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), "Reducibility among Combinatorial Problems", Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, The IBM Research Symposia Series (in English), Boston, MA: Springer US, pp. 85–103, doi:10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अधिकतम_कार्डिनैलिटी_मिलान&oldid=211079’