MINIMUM VERTEX-COVERDescription
Formally, a vertex-cover of an undirected graph is a subset V′ of V such that if edge (u, v) is an edge of G, then u is in V′, or v is in V′, or both. The set V′ is said to "cover" the edges of G. The following figure shows examples of vertex covers in two graphs (and the set V' is marked with red).
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.

Assume that every vertex has an associated cost of .minimize(minimize the total cost)subject tofor all (cover every edge of the graph)for all .(every vertex is either in the vertex cover or not)

Python implementation(running-time: exponential)

import itertools
class Vertex_Cover:
def __init__(self, graph):
self.graph = graph
def validity_check(self, cover):
is_valid = Truefor i in range(len(self.graph)):
…

## Comments

## Post a Comment