Posts

Showing posts from July, 2015

Vertex Cover (python implementation)

Image
MINIMUM VERTEX-COVER Description 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)):���…