**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 to for 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 = True for i in range(len(self.graph)): for j in range(i+1, len(self.graph[i])): if self.graph[i][j] == 1 and cover[i] != '1' and cover[j] != '1': return False return is_valid def vertex_cover_naive(self): n = len(self.graph) minimum_vertex_cover = n a = list(itertools.product(*["01"] * n)) for i in a: if Vertex_Cover.validity_check(ins, i): counter = 0 for value in i: if value == '1': counter += 1 minimum_vertex_cover = min(counter, minimum_vertex_cover) return minimum_vertex_cover if __name__ == '__main__': graph =[[0, 1, 1, 1, 1],[1, 0, 0, 0, 1],[1, 0, 0, 1, 1], [1, 0, 1, 0, 1], [1, 1, 1, 1, 0]] ins = Vertex_Cover(graph) print 'the minimum vertex-cover is:', Vertex_Cover.vertex_cover_naive(ins)

## No comments:

## Post a Comment