Bài Toán Vertex Cover Trên Cây Nhị Phân

Giới thiệu

Vertex cover của đồ thị vô hướng là tập đỉnh sao cho mọi cạnh đều có ít nhất một đỉnh trong tập. Trên cây nhị phân, có thể giải bằng đệ quy + nhớ (memoization).

Đầu vào và Đầu ra

Đầu vào: Cây nhị phân (hình ảnh minh họa).
Đầu ra: Vertex cover tối thiểu = 3.

Thuật toán Đệ quy

Với mỗi nút, xét hai trường hợp: nút đó trong vertex cover (withRoot) hoặc không (withoutRoot). Nếu có root: 1 + vertexCover(left) + vertexCover(right). Nếu không có root: phải lấy cả hai con của left và right (nếu có). Chọn min của hai trường hợp.

vertexCover(root)
Begin
    if root = NULL return 0
    if root không có con return 0
    if vCover(root) != 0 return vCover(root)
    withRoot = 1 + vertexCover(left) + vertexCover(right)
    withoutRoot = 0
    if left != NULL then withoutRoot += 1 + vertexCover(left->left) + vertexCover(left->right)
    if right != NULL then withoutRoot += 1 + vertexCover(right->left) + vertexCover(right->right)
    vCover(root) = min(withRoot, withoutRoot)
    return vCover(root)
End

Ví dụ C++

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int data, vCover;
    node *left, *right;
};

node* getNode(int data) {
    node* n = new node;
    n->data = data; n->vCover = 0;
    n->left = n->right = NULL;
    return n;
}

int vertexCover(node* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 0;
    if (root->vCover) return root->vCover;
    int withRoot = 1 + vertexCover(root->left) + vertexCover(root->right);
    int withoutRoot = 0;
    if (root->left)
        withoutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
    if (root->right)
        withoutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);
    root->vCover = min(withRoot, withoutRoot);
    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 << "Vertex cover tối thiểu: " << vertexCover(root);
    return 0;
}

Kết quả

Vertex cover tối thiểu: 3