একটি অনির্দেশিত গ্রাফের জন্য, ভার্টেক্স কভার হল ভেরটেক্সের একটি সাবসেট, যেখানে গ্রাফের প্রতিটি এজ (u, v)-র জন্য u বা v সেটে থাকে।
বাইনারি ট্রি ব্যবহার করে ভার্টেক্স কভার সমস্যা সহজে সমাধান করা যায়।
এই সমস্যাকে দুটি সাব-প্রব্লেমে ভাগ করা যায়। যখন রুট ভার্টেক্স কভারের অংশ। এই কেসে রুট সকল চাইল্ড এজ কভার করে। আমরা সহজে বাম এবং ডান সাব-ট্রির ভার্টেক্স কভারের আকার বের করে রুটের জন্য ১ যোগ করতে পারি।
ইনপুট এবং আউটপুট
ইনপুট: একটি বাইনারি ট্রি।আউটপুট: ভার্টেক্স কভার ৩।
অ্যালগরিদম
vertexCover(root node)
এই সমস্যায় একটি বাইনারি ট্রি গঠন করা হবে, প্রতিটি নোড ডেটা এবং সেটির দ্বারা কভার করা ভার্টেক্স সংখ্যা ধারণ করবে।
ইনপুট: বাইনারি ট্রির রুট।
আউটপুট: রুট দ্বারা কভার করা ভার্টেক্স সংখ্যা।
শুরু
যদি root φ হয়, তবে
ফেরত দিন 0
যদি root-এর কোনো চাইল্ড নেই, তবে
ফেরত দিন 0
যদি vCover(root) ≠ 0 হয়, তবে
ফেরত দিন vCover(root)
withRoot := 1 + vertexCover(left(root)) + vertexCover(right(root))
withoutRoot := 0
যদি root-এর বাম চাইল্ড থাকে, তবে
withoutRoot := withoutRoot + vertexCover(left(left(root))) + vertexCover(left(right(root)))
যদি root-এর ডান চাইল্ড থাকে, তবে
withoutRoot := withoutRoot + vertexCover(right(left(root))) + vertexCover(right(right(root)))
vCover(root) := min(withRoot, withoutRoot)
ফেরত দিন vCover(root)
শেষ
উদাহরণ (C++)
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int data;
int vCover;
node *left, *right;
};
node *getNode(int data) {
node *newNode = new (node);
newNode->data = data;
newNode->vCover = 0;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int vertexCover(node *root) {
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 0;
if(root->vCover != 0) return root->vCover;
int sizeWithRoot = 1 + vertexCover(root->left) + vertexCover(root->right);
int sizeWithOutRoot = 0;
if(root->left != NULL)
sizeWithOutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
if(root->right != NULL)
sizeWithOutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);
root->vCover = (sizeWithRoot < sizeWithOutRoot) ? sizeWithRoot : sizeWithOutRoot;
return root->vCover;
}
int main() {
node *root = getNode(20);
root->left = getNode(8); root->right = getNode(22);
root->left->left = getNode(4); root->left->right = getNode(12);
root->left->right->left = getNode(10); root->left->right->right = getNode(14);
root->right->right = getNode(25);
cout << "Minimal vertex cover: " << vertexCover(root);
}
আউটপুট
Minimal vertex cover: 3
