বাইপার্টাইট ম্যাচিং হলো একটি গ্রাফে এজের একটি সেট এমনভাবে বেছে নেওয়া যাতে সেই সেটে কোনো দুটি এজ একটি এন্ডপয়েন্ট শেয়ার করে না। ম্যাক্সিমাম ম্যাচিং হলো সর্বাধিক সংখ্যক এজ ম্যাচ করা।
যখন ম্যাক্সিমাম ম্যাচ পাওয়া যায়, তখন আর কোনো এজ যোগ করা সম্ভব নয়। যদি একটি এজ ম্যাক্সিমাম ম্যাচড গ্রাফে যোগ করা হয়, তবে সেটি আর ম্যাচিং নয়। একটি বাইপার্টাইট গ্রাফে একাধিক ম্যাক্সিমাম ম্যাচিং সম্ভব।
ইনপুট এবং আউটপুট
ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স। 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)
ইনপুট: শুরুর নোড, ভিজিটেড লিস্ট ট্র্যাক রাখতে, অ্যাসাইন লিস্ট অন্য নোডের সাথে নোড অ্যাসাইন করতে।
আউটপুট: যখন vértices u-এর জন্য ম্যাচিং সম্ভব হয় তখন true ফেরত দেয়।
শুরু
u-র সাথে সংলগ্ন সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
v কে ভিজিটেড চিহ্নিত করুন
যদি v অ্যাসাইন করা না থাকে, অথবা bipartiteMatch(assign[v], visited, assign) true হয়, তবে
assign[v] := u
return true
শেষ লুপ
return false
শেষ
maxMatch(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: ম্যাক্সিমাম ম্যাচের সংখ্যা।
শুরু
প্রাথমিকভাবে কোনো ভার্টেক্স অ্যাসাইন করা নেই
count := 0
M-এ সব আবেদনকারী u এর জন্য, করুন
সব নোডকে অনভিজিটেড করুন
যদি bipartiteMatch(u, visited, assign), তবে
count কে ১ বাড়ান
শেষ লুপ
শেষ
উদাহরণ (C++ কোড)
#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 < N; i++)
assign[i] = -1; // প্রাথমিকভাবে সব চাকরি উপলব্ধ বলে সেট করুন
int jobCount = 0;
for (int u = 0; u < M; u++) {
// সব আবেদনকারীর জন্য
bool visited[N];
for(int i = 0; i < N; i++)
visited[i] = false; // প্রাথমিকভাবে কোনো চাকরি ভিজিটেড নেই
if (bipartiteMatch(u, visited, assign)) // যখন u চাকরি পায়
jobCount++;
}
return jobCount;
}
int main() {
cout << "Maximum number of applicants matching for job: " << maxMatch();
}
আউটপুট
Maximum number of applicants matching for job: 5
