Vấn đề về bìa đỉnh

Đối với đồ thị vô hướng, phần phủ đỉnh là một tập hợp con của các đỉnh, trong đó với mọi cạnh (u, v) của đồ thị hoặc u hoặc v đều nằm trong tập hợp đó.

Sử dụng cây nhị phân, chúng ta có thể dễ dàng giải quyết vấn đề che đỉnh.

Vấn đề này có thể được chia thành hai vấn đề phụ. Khi gốc là một phần của bìa đỉnh. Đối với trường hợp này, gốc bao phủ tất cả các cạnh trẻ em. Chúng ta chỉ cần tìm kích thước của bìa đỉnh cho cây con trái và phải, và thêm 1 cho gốc.

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

Input:
A binary tree.
Output:
The vertex cover is 3.
 

Thuật toán

vertexCover(root node)

Trong bài toán này, một cây nhị phân sẽ được hình thành, mỗi nút sẽ chứa dữ liệu và số đỉnh được bao phủ bởi nút đó.

Đầu vào - Gốc của cây nhị phân.

Đầu ra - Số đỉnh được bao phủ bởi gốc.

Begin
   if root is φ, then
      return 0
   if root has no child, then
      return 0
   if vCover(root) ≠ 0, then
      return vCover(root)
   withRoot := 1 + vertexCover(left(root)) + vertexCover(right(root))
   withoutRoot := 0

   if root has left child, then
      withoutRoot := withoutRoot + vertexCover(left(left(root))) + vertexCover(left(right(root)))
   if root has right child, then
      withoutRoot := withoutRoot + vertexCover(right(left(root))) + vertexCover(right(right(root)))
   return vCover(root)
End

Ví dụ

#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; //set vertex cover to 0
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;    //newly created node
}

int vertexCover(node *root) {
   if(root == NULL)    //when tree is empty
      return 0;
   if(root->left == NULL && root->right == NULL)    //when no other edge from root
      return 0;
         
   if(root->vCover != 0)   //when vertex cover of this node is found, leave that node
      return root->vCover;
         
   int sizeWithRoot = 1 + vertexCover(root->left) + vertexCover(root->right);
   int sizeWithOutRoot = 0;
   
   if(root->left != NULL)   //when root is not included and go for left child
      sizeWithOutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
   if(root->right != NULL)    //when root is not included and go for right child
      sizeWithOutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);
   
   root->vCover = (sizeWithRoot < sizeWithOutRoot)?sizeWithRoot:sizeWithOutRoot; //minimum vertex cover
   return root->vCover;
}

int main() {
   //create tree to check vertex cover
   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);
}

Đầu ra

Minimal vertex cover: 3