द्विभाजित मिलान एक ग्राफ में किनारों का एक समुच्चय है जिसे इस तरह चुना जाता है कि उस समुच्चय में कोई भी दो किनारे एक अंतिम बिंदु साझा नहीं करेंगे। अधिकतम मिलान किनारों की अधिकतम संख्या का मिलान है।
जब अधिकतम मिलान मिल जाता है, तो हम दूसरा किनारा नहीं जोड़ सकते। यदि एक किनारा अधिकतम मिलान वाले ग्राफ में जोड़ा जाता है, तो यह अब मिलान नहीं रह जाता। एक द्विभाजित ग्राफ के लिए, एक से अधिक अधिकतम मिलान संभव हो सकते हैं।
इनपुट और आउटपुट
इनपुट: आसन्नता मैट्रिक्स। 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 आउटपुट: नौकरी के लिए आवेदकों का अधिकतम मिलान: 5
एल्गोरिदम
bipartiteMatch(u, visited, assign)
इनपुट: प्रारंभिक नोड, ट्रैक रखने के लिए देखी गई सूची, नोड को दूसरे नोड के साथ असाइन करने के लिए असाइन सूची।
आउटपुट: जब शीर्ष u के लिए मिलान संभव हो तो सच वापस करता है।
शुरू u के साथ आसन्न सभी शीर्ष v के लिए, करें यदि v देखा नहीं गया है, तो v को देखा गया चिह्नित करें यदि v असाइन नहीं किया गया है, या bipartiteMatch(assign[v], visited, assign) सच है, तो assign[v] := u वापस करें सच किया वापस करें गलत अंत
maxMatch(graph)
इनपुट: दिया गया ग्राफ।
आउटपुट: मिलान की अधिकतम संख्या।
शुरू प्रारंभ में कोई शीर्ष असाइन नहीं किया गया है count := 0 M में सभी आवेदक u के लिए, करें सभी नोड्स को अनदेखा करें यदि bipartiteMatch(u, visited, assign), तो count को 1 से बढ़ाएं किया अंत
उदाहरण
#include <iostream> #define M 6 #define N 6 using namespace std; bool bipartiteGraph[M][N] = { //M आवेदक और N नौकरियों वाला ग्राफ {0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1} }; bool bipartiteMatch(int u, bool visited[], int assign[]) { for (int v = 0; v < N; v++) { //सभी नौकरियों 0 से N-1 के लिए if (bipartiteGraph[u][v] && !visited[v]) { //जब नौकरी v नहीं देखी गई और u रुचि रखता है visited[v] = true; //नौकरी v को देखा गया चिह्नित करें //जब v असाइन नहीं किया गया या पहले असाइन किया गया if (assign[v] < 0 || bipartiteMatch(assign[v], visited, assign)) { assign[v] = u; //नौकरी v को आवेदक u को असाइन करें return true; } } } return false; } int maxMatch() { int assign[N]; //एक सरणी जो ट्रैक करती है कि कौन सी नौकरी किस आवेदक को असाइन की गई है for(int i = 0; i
आउटपुट
Maximum number of applicants matching for job: 5
