### Vertex Cover (python implementation)

**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)):���…*