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. Puede haber muchas cubiertas de vértices posibles para un gráfico.
Problema Encuentra el tamaño de la cobertura de vértice de tamaño mínimo, es decir, la cardinalidad de una cobertura de vértice con cardinalidad mínima, para un grafo conectado no dirigido con V vértices y m aristas.
Ejemplos:
Input: V = 6, E = 6
6
/
/
1 -----5
/|\
3 | \
\ | \
2 4
Output: Minimum vertex cover size = 2
Consider subset of vertices {1, 2}, every edge
in above graph is either incident on vertex 1
or 2. Hence the minimum vertex cover = {1, 2},
the size of which is 2.
Input: V = 6, E = 7
2 ---- 4 ---- 6
/| |
1 | |
\| |
3 ---- 5
Output: Minimum vertex cover size = 3
Consider subset of vertices {2, 3, 4}, every
edge in above graph is either incident on
vertex 2, 3 or 4. Hence the minimum size of
a vertex cover can be 3.
Método 1 (Ingenuo) Podemos verificar en tiempo O(E + V) si un subconjunto dado de vértices es una cubierta de vértice o no, usando el siguiente algoritmo.
Generate all 2V subsets of vertices in graph and do following for every subset. 1. edges_covered = 0 2. for each vertex in current subset 3. for all edges emerging out of current vertex 4. if the edge is not already marked visited 5. mark the edge visited 6. edges_covered++ 7. if edges_covered is equal to total number edges 8. return size of current subset
Un límite superior en la complejidad temporal de esta solución es O((E + V) * 2 V )
Método 2 (búsqueda binaria) Si generamos subconjuntos de 2 V primero generando subconjuntos V C V , luego subconjuntos V C (V-1) , y así sucesivamente hasta subconjuntos V C 0 (2 V = V C V + V C (V -1) + … + V C 1 + V C 0 ). Nuestro objetivo ahora es encontrar el k mínimo tal que al menos un subconjunto de tamaño ‘k’ entre V C ksubconjuntos es una cobertura de vértices [ Sabemos que si la cobertura de vértices de tamaño mínimo es de tamaño k, entonces existirá una cobertura de vértices de todos los tamaños mayores que k. Es decir, habrá una cubierta de vértice de tamaño k + 1, k + 2, k + 3, …, n. ] Ahora imaginemos una array booleana de tamaño n y llamémosla isCover[]. Así que si la respuesta de la pregunta; «¿Existe una cubierta de vértice de tamaño x?» es sí, ponemos un ‘1’ en la posición x, de lo contrario ‘0’. La array isCover[] se verá así:
| 1 | 2 | 3 | . | . | . | k | . | . | . | norte |
| 0 | 0 | 0 | . | . | . | 1 | . | . | . | 1 |
La array está ordenada y, por lo tanto, se puede realizar una búsqueda binaria, ya que ningún índice antes de k tendrá un ‘1’, y cada índice después de k (inclusive) tendrá un ‘1’, por lo que k es la respuesta. Entonces podemos aplicar la búsqueda binaria para encontrar el conjunto de vértices de tamaño mínimo que cubre todos los bordes (este problema es equivalente a encontrar el último 1 en isCover[]). Ahora el problema es cómo generar todos los subconjuntos de un tamaño dado. La idea es usar el truco de Gosper.
¿Qué es el truco de Gosper? El truco de Gosper es una técnica para obtener el siguiente número con el mismo número de bits establecidos. Así que configuramos los primeros x bits desde la derecha y generamos el siguiente número con x bits configurados hasta que el número sea inferior a 2 V. De esta forma, podemos generar todos los números V Cx con x bits configurados.
CPP
int set = (1 << k) - 1;
int limit = (1 << V);
while (set < limit)
{
// Do your stuff with current set
doStuff(set);
// Gosper's hack:
int c = set & -set;
int r = set + c;
set = (((r^set) >>> 2) / c) | r;
}
Fuente: StackExchange Usamos el truco de gosper para generar todos los subconjuntos de tamaño x (0 < x <= V), es decir, para comprobar si tenemos un ‘1’ o un ‘0’ en cualquier índice x en la array isCover[].
C++
// A C++ program to find size of minimum vertex
// cover using Binary Search
#include<bits/stdc++.h>
#define maxn 25
using namespace std;
// Global array to store the graph
// Note: since the array is global, all the
// elements are 0 initially
bool gr[maxn][maxn];
// Returns true if there is a possible subset
// of size 'k' that can be a vertex cover
bool isCover(int V, int k, int E)
{
// Set has first 'k' bits high initially
int set = (1 << k) - 1;
int limit = (1 << V);
// to mark the edges covered in each subset
// of size 'k'
bool vis[maxn][maxn];
while (set < limit)
{
// Reset visited array for every subset
// of vertices
memset(vis, 0, sizeof vis);
// set counter for number of edges covered
// from this subset of vertices to zero
int cnt = 0;
// selected vertex cover is the indices
// where 'set' has its bit high
for (int j = 1, v = 1 ; j < limit ; j = j << 1, v++)
{
if (set & j)
{
// Mark all edges emerging out of this
// vertex visited
for (int k = 1 ; k <= V ; k++)
{
if (gr[v][k] && !vis[v][k])
{
vis[v][k] = 1;
vis[k][v] = 1;
cnt++;
}
}
}
}
// If the current subset covers all the edges
if (cnt == E)
return true;
// Generate previous combination with k bits high
// set & -set = (1 << last bit high in set)
int c = set & -set;
int r = set + c;
set = (((r^set) >> 2) / c) | r;
}
return false;
}
// Returns answer to graph stored in gr[][]
int findMinCover(int n, int m)
{
// Binary search the answer
int left = 1, right = n;
while (right > left)
{
int mid = (left + right) >> 1;
if (isCover(n, mid, m) == false)
left = mid + 1;
else
right = mid;
}
// at the end of while loop both left and
// right will be equal,/ as when they are
// not, the while loop won't exit the minimum
// size vertex cover = left = right
return left;
}
// Inserts an edge in the graph
void insertEdge(int u, int v)
{
gr[u][v] = 1;
gr[v][u] = 1; // Undirected graph
}
// Driver code
int main()
{
/*
6
/
1 ----- 5 vertex cover = {1, 2}
/|\
3 | \
\ | \
2 4 */
int V = 6, E = 6;
insertEdge(1, 2);
insertEdge(2, 3);
insertEdge(1, 3);
insertEdge(1, 4);
insertEdge(1, 5);
insertEdge(1, 6);
cout << "Minimum size of a vertex cover = "
<< findMinCover(V, E) << endl;
// Let us create another graph
memset(gr, 0, sizeof gr);
/*
2 ---- 4 ---- 6
/| |
1 | | vertex cover = {2, 3, 4}
\ | |
3 ---- 5 */
V = 6, E = 7;
insertEdge(1, 2);
insertEdge(1, 3);
insertEdge(2, 3);
insertEdge(2, 4);
insertEdge(3, 5);
insertEdge(4, 5);
insertEdge(4, 6);
cout << "Minimum size of a vertex cover = "
<< findMinCover(V, E) << endl;
return 0;
}
Java
// A Java program to find size of minimum vertex
// cover using Binary Search
class GFG
{
static final int maxn = 25;
// Global array to store the graph
// Note: since the array is global, all the
// elements are 0 initially
static boolean [][]gr = new boolean[maxn][maxn];
// Returns true if there is a possible subset
// of size 'k' that can be a vertex cover
static boolean isCover(int V, int k, int E)
{
// Set has first 'k' bits high initially
int set = (1 << k) - 1;
int limit = (1 << V);
// to mark the edges covered in each subset
// of size 'k'
boolean [][]vis = new boolean[maxn][maxn];;
while (set < limit)
{
// Reset visited array for every subset
// of vertices
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
{
vis[i][j] = false;
}
}
// set counter for number of edges covered
// from this subset of vertices to zero
int cnt = 0;
// selected vertex cover is the indices
// where 'set' has its bit high
for (int j = 1, v = 1 ; j < limit ; j = j << 1, v++)
{
if ((set & j) != 0)
{
// Mark all edges emerging out of this
// vertex visited
for (int co = 1 ; co <= V ; co++)
{
if (gr[v][co] && !vis[v][co])
{
vis[v][co] = true;
vis[co][v] = true;
cnt++;
}
}
}
}
// If the current subset covers all the edges
if (cnt == E)
return true;
// Generate previous combination with k bits high
// set & -set = (1 << last bit high in set)
int co = set & -set;
int ro = set + co;
set = (((ro^set) >> 2) / co) | ro;
}
return false;
}
// Returns answer to graph stored in gr[][]
static int findMinCover(int n, int m)
{
// Binary search the answer
int left = 1, right = n;
while (right > left)
{
int mid = (left + right) >> 1;
if (isCover(n, mid, m) == false)
left = mid + 1;
else
right = mid;
}
// at the end of while loop both left and
// right will be equal,/ as when they are
// not, the while loop won't exit the minimum
// size vertex cover = left = right
return left;
}
// Inserts an edge in the graph
static void insertEdge(int u, int v)
{
gr[u][v] = true;
gr[v][u] = true; // Undirected graph
}
// Driver code
public static void main(String[] args)
{
/*
6
/
1 ----- 5 vertex cover = {1, 2}
/|\
3 | \
\ | \
2 4 */
int V = 6, E = 6;
insertEdge(1, 2);
insertEdge(2, 3);
insertEdge(1, 3);
insertEdge(1, 4);
insertEdge(1, 5);
insertEdge(1, 6);
System.out.print("Minimum size of a vertex cover = "
+ findMinCover(V, E) +"\n");
// Let us create another graph
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
{
gr[i][j] = false;
}
}
/*
2 ---- 4 ---- 6
/| |
1 | | vertex cover = {2, 3, 4}
\ | |
3 ---- 5 */
V = 6;
E = 7;
insertEdge(1, 2);
insertEdge(1, 3);
insertEdge(2, 3);
insertEdge(2, 4);
insertEdge(3, 5);
insertEdge(4, 5);
insertEdge(4, 6);
System.out.print("Minimum size of a vertex cover = "
+ findMinCover(V, E) +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# A Python3 program to find size of minimum
# vertex cover using Binary Search
# Returns true if there is a possible subSet
# of size 'k' that can be a vertex cover
def isCover(V, k, E):
# Set has first 'k' bits high initially
Set = (1 << k) - 1
limit = (1 << V)
# to mark the edges covered in each
# subSet of size 'k'
vis = [[None] * maxn for i in range(maxn)]
while (Set < limit):
# ReSet visited array for every
# subSet of vertices
vis = [[0] * maxn for i in range(maxn)]
# Set counter for number of edges covered
# from this subSet of vertices to zero
cnt = 0
# selected vertex cover is the
# indices where 'Set' has its bit high
j = 1
v = 1
while(j < limit):
if (Set & j):
# Mark all edges emerging out of
# this vertex visited
for k in range(1, V + 1):
if (gr[v][k] and not vis[v][k]):
vis[v][k] = 1
vis[k][v] = 1
cnt += 1
j = j << 1
v += 1
# If the current subSet covers all the edges
if (cnt == E):
return True
# Generate previous combination with k bits high
# Set & -Set = (1 << last bit high in Set)
c = Set & -Set
r = Set + c
Set = (((r ^ Set) >> 2) // c) | r
return False
# Returns answer to graph stored in gr[][]
def findMinCover(n, m):
# Binary search the answer
left = 1
right = n
while (right > left):
mid = (left + right) >> 1
if (isCover(n, mid, m) == False):
left = mid + 1
else:
right = mid
# at the end of while loop both left and
# right will be equal,/ as when they are
# not, the while loop won't exit the
# minimum size vertex cover = left = right
return left
# Inserts an edge in the graph
def insertEdge(u, v):
gr[u][v] = 1
gr[v][u] = 1 # Undirected graph
# Driver code
maxn = 25
# Global array to store the graph
# Note: since the array is global,
# all the elements are 0 initially
gr = [[None] * maxn for i in range(maxn)]
#
# 6
# /
# 1 ----- 5 vertex cover = {1, 2}
# /|\
# 3 | \
# \ | \
# 2 4
V = 6
E = 6
insertEdge(1, 2)
insertEdge(2, 3)
insertEdge(1, 3)
insertEdge(1, 4)
insertEdge(1, 5)
insertEdge(1, 6)
print("Minimum size of a vertex cover = ",
findMinCover(V, E))
# Let us create another graph
gr = [[0] * maxn for i in range(maxn)]
#
# 2 ---- 4 ---- 6
# /| |
# 1 | | vertex cover = {2, 3, 4}
# \ | |
# 3 ---- 5
V = 6
E = 7
insertEdge(1, 2)
insertEdge(1, 3)
insertEdge(2, 3)
insertEdge(2, 4)
insertEdge(3, 5)
insertEdge(4, 5)
insertEdge(4, 6)
print("Minimum size of a vertex cover = ",
findMinCover(V, E))
# This code is contributed by PranchalK
C#
// A C# program to find size of minimum vertex
// cover using Binary Search
using System;
class GFG
{
static readonly int maxn = 25;
// Global array to store the graph
// Note: since the array is global, all the
// elements are 0 initially
static bool [,]gr = new bool[maxn, maxn];
// Returns true if there is a possible subset
// of size 'k' that can be a vertex cover
static bool isCover(int V, int k, int E)
{
// Set has first 'k' bits high initially
int set = (1 << k) - 1;
int limit = (1 << V);
// to mark the edges covered in each subset
// of size 'k'
bool [,]vis = new bool[maxn, maxn];;
while (set < limit)
{
// Reset visited array for every subset
// of vertices
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
{
vis[i, j] = false;
}
}
// set counter for number of edges covered
// from this subset of vertices to zero
int cnt = 0;
// selected vertex cover is the indices
// where 'set' has its bit high
for (int j = 1, v = 1 ; j < limit ; j = j << 1, v++)
{
if ((set & j) != 0)
{
// Mark all edges emerging out of this
// vertex visited
for (int co = 1 ; co <= V ; co++)
{
if (gr[v, co] && !vis[v, co])
{
vis[v, co] = true;
vis[co, v] = true;
cnt++;
}
}
}
}
// If the current subset covers all the edges
if (cnt == E)
return true;
// Generate previous combination with k bits high
// set & -set = (1 << last bit high in set)
int cO = set & -set;
int rO = set + cO;
set = (((rO^set) >> 2) / cO) | rO;
}
return false;
}
// Returns answer to graph stored in gr[,]
static int findMinCover(int n, int m)
{
// Binary search the answer
int left = 1, right = n;
while (right > left)
{
int mid = (left + right) >> 1;
if (isCover(n, mid, m) == false)
left = mid + 1;
else
right = mid;
}
// at the end of while loop both left and
// right will be equal,/ as when they are
// not, the while loop won't exit the minimum
// size vertex cover = left = right
return left;
}
// Inserts an edge in the graph
static void insertEdge(int u, int v)
{
gr[u, v] = true;
gr[v, u] = true; // Undirected graph
}
// Driver code
public static void Main(String[] args)
{
/*
6
/
1 ----- 5 vertex cover = {1, 2}
/|\
3 | \
\ | \
2 4 */
int V = 6, E = 6;
insertEdge(1, 2);
insertEdge(2, 3);
insertEdge(1, 3);
insertEdge(1, 4);
insertEdge(1, 5);
insertEdge(1, 6);
Console.Write("Minimum size of a vertex cover = "
+ findMinCover(V, E) +"\n");
// Let us create another graph
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
{
gr[i,j] = false;
}
}
/*
2 ---- 4 ---- 6
/| |
1 | | vertex cover = {2, 3, 4}
\ | |
3 ---- 5 */
V = 6;
E = 7;
insertEdge(1, 2);
insertEdge(1, 3);
insertEdge(2, 3);
insertEdge(2, 4);
insertEdge(3, 5);
insertEdge(4, 5);
insertEdge(4, 6);
Console.Write("Minimum size of a vertex cover = "
+ findMinCover(V, E) +"\n");
}
}
// This code is contributed by Rajput-Ji
Minimum size of a vertex cover = 2 Minimum size of a vertex cover = 3
Conclusión: Complejidad de tiempo: O (E * ( V C V/2 + V C V/4 + V C V/8 +…hasta V C k ) ) Estos términos no son más que log(V) en el peor de los casos.
Nota: el truco de Gosper funciona solo hasta V = 31, si tomamos ‘long long int’ en lugar de ‘int’, puede funcionar hasta V = 63. Saumye Malhotra contribuye con este artículo .
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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