ভার্টেক্স কভার (Vertex Cover) — নোডের একটি সেট যাতে গ্রাফের প্রতিটি এজ কমপক্ষে একটি নোডের সাথে ইনসিডেন্ট থাকে। মিনিমাম ভার্টেক্স কভার — সবচোয় ছোট যেই সেট।
অ্যালগরিদম (বাইনারি সার্চ + বিটমাস্ক)
- সাইজ
kএর ভার্টেক্স কভার আছে কিনা চেক করুন (বিটমাস্ক সব সাবসেট ট্রাই করে)। - বাইনারি সার্চ দিয়ে ন্যূনতম
kখুঁজুন (১ থেকে V)।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define MAX 15
bool adj[MAX][MAX];
bool check_cover(int V, int k, int E) {
int set = (1<>2)/c) | r; // Next combination (Gosper's hack)
}
return false;
}
int find_cover(int V, int E) {
int lo = 1, hi = V;
while (hi > lo) {
int mid = (lo+hi)>>1;
if (!check_cover(V, mid, E)) lo = mid+1;
else hi = mid;
}
return lo;
}
void add_edge(int u, int v) { adj[u][v] = adj[v][u] = 1; }
int main() {
memset(adj, 0, sizeof adj);
int V=6, E=5;
add_edge(2,3); add_edge(2,4); add_edge(3,5);
add_edge(4,5); add_edge(4,6);
cout << "Size of Minimum Vertex Cover: " << find_cover(V, E) << endl;
return 0;
}
আউটপুট
Size of Minimum Vertex Cover: 2
