Data Structures Algorithms 简明教程

Vertex Cover Algorithm

你是否曾思考过交通摄像头的放置问题？例如，如何在不过度浪费政府预算的情况下有效地安放摄像头？这个问题的答案就是 vertex-cover algorithm 。摄像头的放置方式是力求让一个摄像头覆盖尽可能多的道路，也就是，选择交叉口，并确保摄像头覆盖尽可能大的区域。

Have you ever wondered about the placement of traffic cameras? That how they are efficiently placed without wasting too much budget from the government? The answer to that comes in the form of vertex-cover algorithm. The positions of the cameras are chosen in such a way that one camera covers as many roads as possible, i.e., we choose junctions and make sure the camera covers as much area as possible.

无向图 G = (V,E) 的一个 vertex-cover 是图的顶点的子集，对于图中的所有边 (u,v) ， мають u and v ∈ V 。交汇点被视为图的节点，道路被视为边。该算法找出覆盖最大数量道路的最小交汇点集合。

A vertex-cover of an undirected graph G = (V,E) is the subset of vertices of the graph such that, for all the edges (u,v) in the graph,u and v ∈ V. The junction is treated as the node of a graph and the roads as the edges. The algorithm finds the minimum set of junctions that cover maximum number of roads.

这是一个最小化问题，因为我们要找出最小规模的顶点覆盖 − 顶点覆盖的规模是其中包含顶点的数量。优化问题是一个 NP 完备问题，因此无法在多项式时间内求解；但可以在多项式时间内找出近似最优解。

It is a minimization problem since we find the minimum size of the vertex cover – the size of the vertex cover is the number of vertices in it. The optimization problem is an NP-Complete problem and hence, cannot be solved in polynomial time; but what can be found in polynomial time is the near optimal solution.

Vertex Cover Algorithm

顶点覆盖近似算法以无向图作为输入，并执行此算法以获得一个集合，该集合的大小肯定刚好是最佳顶点覆盖的两倍。

The vertex cover approximation algorithm takes an undirected graph as an input and is executed to obtain a set of vertices that is definitely twice as the size of optimal vertex cover.

顶点覆盖是一种 2-近似算法。

The vertex cover is a 2-approximation algorithm.

Algorithm

Step 1 − 从输入图中选择任意一条随机边，并将该边的各个顶点相邻的边全部标记。

Step 1 − Select any random edge from the input graph and mark all the edges that are incident on the vertices corresponding to the selected edge.

Step 2 − 将随机边的各个顶点添加到输出集中。

Step 2 − Add the vertices of the arbitrary edge to an output set.

Step 3 − 对图中剩下的未标记边重复第 1 步，并将其添加到输出集中直到无边未标记。

Step 3 − Repeat Step 1 on the remaining unmarked edges of the graph and add the vertices chosen to the output until there’s no edge left unmarked.

Step 4 − 最后的输出集将会是接近最优的顶点覆盖。

Step 4 − The final output set achieved would be the near-optimal vertex cover.

Pseudocode

APPROX-VERTEX_COVER (G: Graph)
c ← { }
E’ ← E[G]
while E’ is not empty do
   Let (u, v) be an arbitrary edge of E’
   c ← c U {u, v}
   Remove from E’ every edge incident on either u or v
return c

Example

给定图的边集为 −

The set of edges of the given graph is −

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,5),(8,5)}

现在，我们从选择任意边 (1,6) 开始。我们消除与顶点 1 或 6 相邻的所有边，并添加边 (1,6) 进行覆盖。

Now, we start by selecting an arbitrary edge (1,6). We eliminate all the edges, which are either incident to vertex 1 or 6 and we add edge (1,6) to cover.