Una cubierta de vértices de un gráfico no dirigido es un subconjunto de sus vértices, de modo que para cada borde (u, v) del gráfico, ‘u’ o ‘v’ están en la cubierta de vértices. Aunque el nombre es Vertex Cover, el conjunto cubre todos los bordes del gráfico dado.
El problema para encontrar la cobertura de vértice de tamaño mínimo de un gráfico es NP completo . Pero se puede resolver en tiempo polinomial para árboles. En esta publicación se analiza una solución para Binary Tree. La misma solución se puede extender para árboles n-arios.
Por ejemplo, considere el siguiente árbol binario. La cobertura de vértice más pequeña es {20, 50, 30} y el tamaño de la cobertura de vértice es 3.
La idea es considerar seguir dos posibilidades para la raíz y recursivamente para todos los Nodes de la raíz.
1) La raíz es parte de la cubierta de vértices: en este caso, la raíz cubre todos los bordes secundarios. Calculamos recursivamente el tamaño de las cubiertas de vértices para los subárboles izquierdo y derecho y agregamos 1 al resultado (para la raíz).
2) La raíz no es parte de la cobertura de vértices: en este caso, ambos elementos secundarios de la raíz deben incluirse en la cobertura de vértices para cubrir todos los bordes de la raíz a los elementos secundarios. Calculamos recursivamente el tamaño de las cubiertas de vértices de todos los nietos y el número de hijos del resultado (para dos hijos de la raíz).
A continuación se muestra la implementación de la idea anterior.
C
// A naive recursive C implementation for vertex cover problem for a tree
#include <stdio.h>
#include <stdlib.h>
// A utility function to find min of two integers
int min(int x, int y) { return (x < y)? x: y; }
/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node
{
int data;
struct node *left, *right;
};
// The function returns size of the minimum vertex cover
int vCover(struct node *root)
{
// The size of minimum vertex cover is zero if tree is empty or there
// is only one node
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
// Calculate size of vertex cover when root is part of it
int size_incl = 1 + vCover(root->left) + vCover(root->right);
// Calculate size of vertex cover when root is not part of it
int size_excl = 0;
if (root->left)
size_excl += 1 + vCover(root->left->left) + vCover(root->left->right);
if (root->right)
size_excl += 1 + vCover(root->right->left) + vCover(root->right->right);
// Return the minimum of two sizes
return min(size_incl, size_excl);
}
// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);
printf ("Size of the smallest vertex cover is %d ", vCover(root));
return 0;
}
Java
// A naive recursive Java implementation
// for vertex cover problem for a tree
class GFG
{
// A utility function to find min of two integers
static int min(int x, int y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
static class node
{
int data;
node left, right;
};
// The function returns size
// of the minimum vertex cover
static int vCover(node root)
{
// The size of minimum vertex cover
// is zero if tree is empty or there
// is only one node
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 0;
// Calculate size of vertex cover
// when root is part of it
int size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
int size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Return the minimum of two sizes
return Math.min(size_incl, size_excl);
}
// A utility function to create a node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void main(String[] args)
{
// Let us construct tree given in the above diagram
node root = newNode(20);
root.left = newNode(8);
root.left.left = newNode(4);
root.left.right = newNode(12);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
root.right = newNode(22);
root.right.right = newNode(25);
System.out.printf("Size of the smallest vertex" +
"cover is %d ", vCover(root));
}
}
// This code is contributed by 29AjayKumar
Python3
# A naive recursive Python3 implementation
# for vertex cover problem for a tree
# A utility function to find min of two integers
# A binary tree node has data, pointer to
# left child and a pointer to right child
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
# The function returns size of
# the minimum vertex cover
def vCover(root):
# The size of minimum vertex cover
# is zero if tree is empty or there
# is only one node
if (root == None):
return 0
if (root.left == None and
root.right == None):
return 0
# Calculate size of vertex cover when
# root is part of it
size_incl = (1 + vCover(root.left) +
vCover(root.right))
# Calculate size of vertex cover
# when root is not part of it
size_excl = 0
if (root.left):
size_excl += (1 + vCover(root.left.left) +
vCover(root.left.right))
if (root.right):
size_excl += (1 + vCover(root.right.left) +
vCover(root.right.right))
# Return the minimum of two sizes
return min(size_incl, size_excl)
# Driver Code
if __name__ == '__main__':
# Let us construct the tree
# given in the above diagram
root = Node(20)
root.left = Node(8)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right = Node(22)
root.right.right = Node(25)
print("Size of the smallest vertex cover is", vCover(root))
# This code is contributed by mohit kumar 29
C#
// A naive recursive C# implementation
// for vertex cover problem for a tree
using System;
class GFG
{
// A utility function to find
// min of two integers
static int min(int x, int y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
public class node
{
public int data;
public node left, right;
};
// The function returns size
// of the minimum vertex cover
static int vCover(node root)
{
// The size of minimum vertex cover
// is zero if tree is empty or there
// is only one node
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
return 0;
// Calculate size of vertex cover
// when root is part of it
int size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
int size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Return the minimum of two sizes
return Math.Min(size_incl, size_excl);
}
// A utility function to create a node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void Main(String[] args)
{
// Let us construct tree given
// in the above diagram
node root = newNode(20);
root.left = newNode(8);
root.left.left = newNode(4);
root.left.right = newNode(12);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
root.right = newNode(22);
root.right.right = newNode(25);
Console.Write("Size of the smallest vertex" +
"cover is {0} ", vCover(root));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A naive recursive Javascript implementation
// for vertex cover problem for a tree
// A utility function to find min of two integers
function min(x,y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
class Node
{
constructor(d)
{
this.data=d;
this.left=null;
this.right=null;
}
}
// The function returns size
// of the minimum vertex cover
function vCover(root)
{
// The size of minimum vertex cover
// is zero if tree is empty or there
// is only one node
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 0;
// Calculate size of vertex cover
// when root is part of it
let size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
let size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Return the minimum of two sizes
return Math.min(size_incl, size_excl);
}
// Driver code
// Let us construct tree given in the above diagram
root = new Node(20);
root.left = new Node(8);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
root.right = new Node(22);
root.right.right = new Node(25);
document.write("Size of the smallest vertex" +
"cover is ", vCover(root));
// This code is contributed by unknown2108
</script>
Producción:
Size of the smallest vertex cover is 3
La complejidad temporal del enfoque recursivo ingenuo anterior es exponencial. Cabe señalar que la función anterior calcula los mismos subproblemas una y otra vez. Por ejemplo, vCover del Node con valor 50 se evalúa dos veces, ya que 50 es nieto de 10 e hijo de 20.
Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema Vertex Cover tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP), los cálculos de los mismos subproblemas se pueden evitar almacenando las soluciones a los subproblemas y resolviendo los problemas de manera ascendente.
A continuación se muestra la implementación de la solución basada en la programación dinámica. En la siguiente solución, se agrega un campo adicional ‘vc’ a los Nodes del árbol. El valor inicial de ‘vc’ se establece en 0 para todos los Nodes. La función recursiva vCover() calcula ‘vc’ para un Node solo si aún no está configurado.
C
/* Dynamic programming based program for Vertex Cover problem for
a Binary Tree */
#include <stdio.h>
#include <stdlib.h>
// A utility function to find min of two integers
int min(int x, int y) { return (x < y)? x: y; }
/* A binary tree node has data, pointer to left child and a pointer to
right child */
struct node
{
int data;
int vc;
struct node *left, *right;
};
// A memoization based function that returns size of the minimum vertex cover.
int vCover(struct node *root)
{
// The size of minimum vertex cover is zero if tree is empty or there
// is only one node
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
// If vertex cover for this node is already evaluated, then return it
// to save recomputation of same subproblem again.
if (root->vc != 0)
return root->vc;
// Calculate size of vertex cover when root is part of it
int size_incl = 1 + vCover(root->left) + vCover(root->right);
// Calculate size of vertex cover when root is not part of it
int size_excl = 0;
if (root->left)
size_excl += 1 + vCover(root->left->left) + vCover(root->left->right);
if (root->right)
size_excl += 1 + vCover(root->right->left) + vCover(root->right->right);
// Minimum of two values is vertex cover, store it before returning
root->vc = min(size_incl, size_excl);
return root->vc;
}
// A utility function to create a node
struct node* newNode( int data )
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
temp->vc = 0; // Set the vertex cover as 0
return temp;
}
// Driver program to test above functions
int main()
{
// Let us construct the tree given in the above diagram
struct node *root = newNode(20);
root->left = newNode(8);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
root->right = newNode(22);
root->right->right = newNode(25);
printf ("Size of the smallest vertex cover is %d ", vCover(root));
return 0;
}
Java
/* Dynamic programming based program for
Vertex Cover problem for a Binary Tree */
class GFG
{
// A utility function to find min of two integers
static int min(int x, int y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
static class node
{
int data;
int vc;
node left, right;
};
// A memoization based function that returns
// size of the minimum vertex cover.
static int vCover(node root)
{
// The size of minimum vertex cover is zero
// if tree is empty or there is only one node
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 0;
// If vertex cover for this node is
// already evaluated, then return it
// to save recomputation of same subproblem again.
if (root.vc != 0)
return root.vc;
// Calculate size of vertex cover
// when root is part of it
int size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
int size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Minimum of two values is vertex cover,
// store it before returning
root.vc = Math.min(size_incl, size_excl);
return root.vc;
}
// A utility function to create a node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
temp.vc = 0; // Set the vertex cover as 0
return temp;
}
// Driver code
public static void main(String[] args)
{
// Let us construct tree given in the above diagram
node root = newNode(20);
root.left = newNode(8);
root.left.left = newNode(4);
root.left.right = newNode(12);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
root.right = newNode(22);
root.right.right = newNode(25);
System.out.printf("Size of the smallest vertex" +
"cover is %d ", vCover(root));
}
}
// This code is contributed by PrinciRaj1992
C#
/* Dynamic programming based program for
Vertex Cover problem for a Binary Tree */
using System;
class GFG
{
// A utility function to find
// min of two integers
static int min(int x, int y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
class node
{
public int data;
public int vc;
public node left, right;
};
// A memoization based function that returns
// size of the minimum vertex cover.
static int vCover(node root)
{
// The size of minimum vertex cover is zero
// if tree is empty or there is only one node
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
return 0;
// If vertex cover for this node is
// already evaluated, then return it
// to save recomputation of same subproblem again.
if (root.vc != 0)
return root.vc;
// Calculate size of vertex cover
// when root is part of it
int size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
int size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Minimum of two values is vertex cover,
// store it before returning
root.vc = Math.Min(size_incl, size_excl);
return root.vc;
}
// A utility function to create a node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
temp.vc = 0; // Set the vertex cover as 0
return temp;
}
// Driver code
public static void Main(String[] args)
{
// Let us construct tree given in the above diagram
node root = newNode(20);
root.left = newNode(8);
root.left.left = newNode(4);
root.left.right = newNode(12);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
root.right = newNode(22);
root.right.right = newNode(25);
Console.Write("Size of the smallest vertex" +
"cover is {0} ", vCover(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
/* Dynamic programming based program for
Vertex Cover problem for a Binary Tree */
// A utility function to find min of two integers
function min(x,y)
{
return (x < y) ? x : y;
}
/*
* A binary tree node has data, pointer
to left child and a pointer to right
* child
*/
class Node
{
constructor(data)
{
this.vc=0;
this.data=data;
this.left=this.right=null;
}
}
// A memoization based function that returns
// size of the minimum vertex cover.
function vCover(root)
{
// The size of minimum vertex cover is zero
// if tree is empty or there is only one node
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 0;
// If vertex cover for this node is
// already evaluated, then return it
// to save recomputation of same subproblem again.
if (root.vc != 0)
return root.vc;
// Calculate size of vertex cover
// when root is part of it
let size_incl = 1 + vCover(root.left) +
vCover(root.right);
// Calculate size of vertex cover
// when root is not part of it
let size_excl = 0;
if (root.left != null)
size_excl += 1 + vCover(root.left.left) +
vCover(root.left.right);
if (root.right != null)
size_excl += 1 + vCover(root.right.left) +
vCover(root.right.right);
// Minimum of two values is vertex cover,
// store it before returning
root.vc = Math.min(size_incl, size_excl);
return root.vc;
}
// Driver code
// Let us construct tree given in the above diagram
let root = new Node(20);
root.left = new Node(8);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
root.right = new Node(22);
root.right.right = new Node(25);
document.write("Size of the smallest vertex " +
"cover is ", vCover(root));
// This code is contributed by rag2127
</script>
Producción:
Size of the smallest vertex cover is 3
Referencias:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf
Ejercicio:
Amplíe la solución anterior para árboles n-arios.
Este artículo es una contribución de Udit Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Enfoque para cualquier árbol general:
1. El enfoque será el mismo enfoque de programación dinámica que se discutió.
2. Para cada Node, si excluimos este Node de la cobertura de vértices, tenemos que incluir sus Nodes vecinos,
y si incluimos este Node en la cubierta de vértice entonces tomaremos el mínimo de las dos posibilidades de tomar su vecino
Nodes en la cobertura de vértices para obtener la cobertura mínima de vértices.
3. Almacenaremos la información anterior en la array dp.
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// An utility function to add an edge in the tree
void addEdge(vector<int> adj[], int x, int y)
{
adj[x].push_back(y);
adj[y].push_back(x);
}
void dfs(vector<int> adj[], vector<int> dp[], int src,
int par)
{
for (auto child : adj[src]) {
if (child != par)
dfs(adj, dp, child, src);
}
for (auto child : adj[src]) {
if (child != par) {
// not including source in the vertex cover
dp[src][0] += dp[child][1];
// including source in the vertex cover
dp[src][1] += min(dp[child][1], dp[child][0]);
}
}
}
// function to find minimum size of vertex cover
void minSizeVertexCover(vector<int> adj[], int N)
{
vector<int> dp[N + 1];
for (int i = 1; i <= N; i++) {
// 0 denotes not included in vertex cover
dp[i].push_back(0);
// 1 denotes included in vertex cover
dp[i].push_back(1);
}
dfs(adj, dp, 1, -1);
// printing minimum size vertex cover
cout << min(dp[1][0], dp[1][1]) << endl;
}
// Driver Code
int main()
{
/* 1
/ \
2 7
/ \
3 6
/ | \
4 8 5
*/
// number of nodes in the tree
int N = 8;
// adjacency list representation of the tree
vector<int> adj[N + 1];
addEdge(adj, 1, 2);
addEdge(adj, 1, 7);
addEdge(adj, 2, 3);
addEdge(adj, 2, 6);
addEdge(adj, 3, 4);
addEdge(adj, 3, 8);
addEdge(adj, 3, 5);
minSizeVertexCover(adj, N);
return 0;
}
Producción
3
Complejidad de tiempo : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA