वर्टेक्स कवर समस्या

एक अनडायरेक्टेड ग्राफ के लिए, वर्टेक्स कवर वर्टेक्स का एक सबसेट है, जहां ग्राफ के प्रत्येक एज (u, v) के लिए या तो u या v सेट में होता है।

बाइनरी ट्री का उपयोग करके, हम वर्टेक्स कवर समस्या को आसानी से हल कर सकते हैं।

इस समस्या को दो सब-प्रॉब्लम्स में विभाजित किया जा सकता है। जब रूट वर्टेक्स कवर का हिस्सा होता है। इस मामले में, रूट सभी बच्चों के एज को कवर करता है। हम बाएं और दाएं सब-ट्री के लिए वर्टेक्स कवर का आकार आसानी से ढूंढ सकते हैं, और रूट के लिए 1 जोड़ सकते हैं।

इनपुट और आउटपुट

इनपुट: एक बाइनरी ट्री।
आउटपुट: वर्टेक्स कवर 3 है।

एल्गोरिदम

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)
अंत

उदाहरण (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