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

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

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

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

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

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

• एक स्रोत शीर्ष जोड़ें s, X में प्रत्येक शीर्ष पर s से एक किनारा जोड़ें।
• एक सिंक शीर्ष जोड़ें 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 प्रवाह होता है

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

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

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

$O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).$

आकार के शब्दों पर बूलियन ऑपरेशन का उपयोग करना $\lambda$ जटिलता को और उत्तम बनाया गया है :

$O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).$

विशेष प्रकार के द्विदलीय ग्राफ़ के लिए अधिक कुशल एल्गोरिदम उपस्थित हैं:

• विरल ग्राफ द्विदलीय ग्राफ़ के लिए, अधिकतम मिलान समस्या ${\tilde {O}}(E^{10/7})$ को हल किया जा सकता है विद्युत प्रवाह पर आधारित मैड्री के एल्गोरिदम के साथ। * समतलीय ग्राफ़ द्विदलीय ग्राफ़ के लिए, समस्या O(n log³ n) को समय पर हल किया जा सकता है जहाँ n एकाधिक स्रोतों और सिंक के साथ समस्या को अधिकतम प्रवाह तक कम करके, शीर्षों की संख्या है।

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

ब्लूसोम एल्गोरिथ्म सामान्य (आवश्यक नहीं कि द्विदलीय) ग्राफ़ में अधिकतम-कार्डिनैलिटी मिलान पाता है। यह समय के अनुसार चलता है $O(|V|^{2}\cdot |E|)$. का उत्तम प्रदर्शन O(√VE) सामान्य ग्राफ़ के लिए, द्विदलीय ग्राफ़ पर हॉपक्रॉफ्ट-कार्प एल्गोरिदम के प्रदर्शन से मेल खाते हुए, मिकाली और वज़ीरानी के बहुत अधिक जटिल एल्गोरिदम के साथ प्राप्त किया जा सकता है। वही सीमा नॉर्बर्ट ब्लम (कंप्यूटर वैज्ञानिक) द्वारा एल्गोरिदम द्वारा प्राप्त की गई थी और हेरोल्ड एन. गैबो और रॉबर्ट टार्जन द्वारा एल्गोरिदम। एक वैकल्पिक दृष्टिकोण यादृच्छिक एल्गोरिदम का उपयोग करता है और तेज़ मैट्रिक्स गुणन एल्गोरिदम पर आधारित है। यह जटिलता वाले सामान्य ग्राफ़ $O(V^{2.376})$ के लिए यादृच्छिक एल्गोरिदम देता है . यह पर्याप्त सघन ग्राफ के लिए सिद्धांत रूप में उत्तम है, किन्तु व्यवहार में एल्गोरिथ्म धीमा है।

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

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

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