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. Dado un gráfico no dirigido, el problema de la cobertura de vértices es encontrar la cobertura de vértices de tamaño mínimo .
Los siguientes son algunos ejemplos.
Vertex Cover Problem es un problema NP completo conocido , es decir, no hay una solución en tiempo polinomial para esto a menos que P = NP. Sin embargo, existen algoritmos de tiempo polinómico aproximado para resolver el problema. El siguiente es un algoritmo aproximado simple adaptado del libro CLRS .
Enfoque ingenuo:
Considere todo el subconjunto de vértices uno por uno y descubra si cubre todos los bordes del gráfico. Por ej. en un gráfico que consta de solo 3 vértices, el conjunto que consta de la combinación de vértices es: {0,1,2,{0,1},{0,2},{1,2},{0,1,2}} . Usando cada elemento de este conjunto, compruebe si estos vértices cubren todos los bordes del gráfico. Por lo tanto, actualice la respuesta óptima. Y, por lo tanto, imprima el subconjunto que tenga un número mínimo de vértices que también cubra todos los bordes del gráfico.
Algoritmo aproximado para la cobertura de vértices:
1) Initialize the result as {}
2) Consider a set of all edges in given graph. Let the set be E.
3) Do following while E is not empty
...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
...b) Remove all edges from E which are either incident on u or v.
4) Return result
El siguiente diagrama muestra la ejecución del algoritmo aproximado anterior:
¿Qué tan bien funciona el algoritmo anterior?
Se puede probar que el algoritmo aproximado anterior nunca encuentra una cobertura de vértice cuyo tamaño sea más del doble del tamaño de la cobertura de vértice mínima posible (Consulte esto como prueba)
Implementación:
Las siguientes son implementaciones en C++ y Java del algoritmo aproximado anterior.
C++
// Program to print Vertex Cover of a given undirected graph
#include<iostream>
#include <list>
using namespace std;
// This class represents a undirected graph using adjacency list
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void printVertexCover(); // prints vertex cover
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
adj[w].push_back(v); // Since the graph is undirected
}
// The function to print vertex cover
void Graph::printVertexCover()
{
// Initialize all vertices as not visited.
bool visited[V];
for (int i=0; i<V; i++)
visited[i] = false;
list<int>::iterator i;
// Consider all edges one by one
for (int u=0; u<V; u++)
{
// An edge is only picked when both visited[u] and visited[v]
// are false
if (visited[u] == false)
{
// Go through all adjacents of u and pick the first not
// yet visited vertex (We are basically picking an edge
// (u, v) from remaining edges.
for (i= adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i;
if (visited[v] == false)
{
// Add the vertices (u, v) to the result set.
// We make the vertex u and v visited so that
// all edges from/to them would be ignored
visited[v] = true;
visited[u] = true;
break;
}
}
}
}
// Print the vertex cover
for (int i=0; i<V; i++)
if (visited[i])
cout << i << " ";
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.printVertexCover();
return 0;
}
Java
// Java Program to print Vertex
// Cover of a given undirected graph
import java.io.*;
import java.util.*;
import java.util.LinkedList;
// This class represents an undirected
// graph using adjacency list
class Graph
{
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
adj[w].add(v); //Graph is undirected
}
// The function to print vertex cover
void printVertexCover()
{
// Initialize all vertices as not visited.
boolean visited[] = new boolean[V];
for (int i=0; i<V; i++)
visited[i] = false;
Iterator<Integer> i;
// Consider all edges one by one
for (int u=0; u<V; u++)
{
// An edge is only picked when both visited[u]
// and visited[v] are false
if (visited[u] == false)
{
// Go through all adjacents of u and pick the
// first not yet visited vertex (We are basically
// picking an edge (u, v) from remaining edges.
i = adj[u].iterator();
while (i.hasNext())
{
int v = i.next();
if (visited[v] == false)
{
// Add the vertices (u, v) to the result
// set. We make the vertex u and v visited
// so that all edges from/to them would
// be ignored
visited[v] = true;
visited[u] = true;
break;
}
}
}
}
// Print the vertex cover
for (int j=0; j<V; j++)
if (visited[j])
System.out.print(j+" ");
}
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.printVertexCover();
}
}
// This code is contributed by Aakash Hasija
Python3
# Python3 program to print Vertex Cover # of a given undirected graph from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: def __init__(self, vertices): # No. of vertices self.V = vertices # Default dictionary to store graph self.graph = defaultdict(list) # Function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # The function to print vertex cover def printVertexCover(self): # Initialize all vertices as not visited. visited = [False] * (self.V) # Consider all edges one by one for u in range(self.V): # An edge is only picked when # both visited[u] and visited[v] # are false if not visited[u]: # Go through all adjacents of u and # pick the first not yet visited # vertex (We are basically picking # an edge (u, v) from remaining edges. for v in self.graph[u]: if not visited[v]: # Add the vertices (u, v) to the # result set. We make the vertex # u and v visited so that all # edges from/to them would # be ignored visited[v] = True visited[u] = True break # Print the vertex cover for j in range(self.V): if visited[j]: print(j, end = ' ') print() # Driver code # Create a graph given in # the above diagram g = Graph(7) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 3) g.addEdge(3, 4) g.addEdge(4, 5) g.addEdge(5, 6) g.printVertexCover() # This code is contributed by Prateek Gupta
C#
// C# Program to print Vertex
// Cover of a given undirected
// graph
using System;
using System.Collections.Generic;
// This class represents an
// undirected graph using
// adjacency list
class Graph{
// No. of vertices
public int V;
// Array of lists for
// Adjacency List Representation
public List<int> []adj;
// Constructor
public Graph(int v)
{
V = v;
adj = new List<int>[v];
for (int i = 0; i < v; ++i)
adj[i] = new List<int>();
}
//Function to add an edge
// into the graph
void addEdge(int v, int w)
{
// Add w to v's list.
adj[v].Add(w);
//Graph is undirected
adj[w].Add(v);
}
// The function to print
// vertex cover
void printVertexCover()
{
// Initialize all vertices
// as not visited.
bool []visited = new bool[V];
// Consider all edges one
// by one
for (int u = 0; u < V; u++)
{
// An edge is only picked
// when both visited[u]
// and visited[v] are false
if (visited[u] == false)
{
// Go through all adjacents
// of u and pick the first
// not yet visited vertex
// (We are basically picking
// an edge (u, v) from remaining
// edges.
foreach(int i in adj[u])
{
int v = i;
if (visited[v] == false)
{
// Add the vertices (u, v)
// to the result set. We
// make the vertex u and
// v visited so that all
// edges from/to them would
// be ignored
visited[v] = true;
visited[u] = true;
break;
}
}
}
}
// Print the vertex cover
for (int j = 0; j < V; j++)
if (visited[j])
Console.Write(j + " ");
}
// Driver method
public static void Main(String []args)
{
// Create a graph given in
// the above diagram
Graph g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.printVertexCover();
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to print Vertex
// Cover of a given undirected graph
// This class represents an undirected
// graph using adjacency list
class Graph
{
// Constructor
constructor(v)
{
this.V=v;
this.adj = new Array(v);
for (let i = 0; i < v; ++i)
this.adj[i] = [];
}
// Function to add an edge into the graph
addEdge(v, w)
{
this.adj[v].push(w); // Add w to v's list.
this.adj[w].push(v); //Graph is undirected
}
// The function to print vertex cover
printVertexCover()
{
// Initialize all vertices as not visited.
let visited = new Array(this.V);
for (let i = 0; i < this.V; i++)
visited[i] = false;
// Consider all edges one by one
for (let u = 0; u < this.V; u++)
{
// An edge is only picked when both visited[u]
// and visited[v] are false
if (visited[u] == false)
{
// Go through all adjacents of u and pick the
// first not yet visited vertex (We are basically
// picking an edge (u, v) from remaining edges.
for(let i = 0; i < this.adj[u].length; i++)
{
let v = this.adj[u][i];
if (visited[v] == false)
{
// Add the vertices (u, v) to the result
// set. We make the vertex u and v visited
// so that all edges from/to them would
// be ignored
visited[v] = true;
visited[u] = true;
break;
}
}
}
}
// Print the vertex cover
for (let j = 0; j < this.V; j++)
if (visited[j])
document.write(j+" ");
}
}
// Driver method
// Create a graph given in the above diagram
let g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.printVertexCover();
// This code is contributed by patel2127
</script>
Producción:
0 1 3 4 5 6
La Complejidad de Tiempo del algoritmo anterior es O(V + E).
Algoritmos exactos:
aunque el problema es NP completo, se puede resolver en tiempo polinomial para los siguientes tipos de gráficos.
1) Gráfico bipartito
2) Gráfico de árbol
El problema para verificar si hay una cubierta de vértice de tamaño menor o igual que un número k dado también se puede resolver en tiempo polinomial si k está acotado por O (LogV) (Consulte esto )
Nosotros pronto discutiremos algoritmos exactos para la cobertura de vértices.
Este artículo es una contribución de Shubham . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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