边覆盖

在图论中，图的边覆盖是指一组边的集合，且该集合满足图的每个顶点都在至少一条边上。在计算机科学中，最小边覆盖问题是寻找最小个数边的边覆盖问题。它是属于覆盖问题类的优化问题，可以在多项式时间内求解。

 定义 
正式来说，图G的边覆盖是指一组边的集合C ，其满足G中的每个顶点都至少在C中的一条边上。其被描述为集合C覆盖了G中的所有顶点。下图显示了两个图中边缘覆盖的示例。

File:Edge-cover.svg

最小边覆盖是指最小可能数量的边覆盖。边覆盖数是最小边覆盖的数量。下图中的红线为最小边覆盖的示例。

File:Minimum-edge-cover.svg

注意右图不但是边覆盖，而且是满足匹配的。它是一种特殊情况——完美匹配：在一个匹配M中，每个顶点都恰好只在一条边上。完美匹配（如果存在）一定是最小边覆盖。

 例子 

 所有边的集合(若没有度为 0 的顶点)。
 完全二分图K m, n的边覆盖数为m和n中的较大值。

 算法 
通过找到一个最大基数匹配并贪婪地扩展它直到覆盖所有顶点，可以在多项式时间内找到最小的边缘覆盖。 , p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190. .在下图中，最大基数匹配用红色标记；为覆盖不匹配节点而添加的额外边用蓝色标记。 （右图的最大基数匹配是完美匹配；因此它已经覆盖了所有顶点，不再需要额外的边去覆盖。 )

File:Minimum-edge-cover-from-maximum-matching.svg

另一方面来说，寻找最小点覆盖的相关问题是一个NP困难问题。 , p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190.

 参见 

 顶点覆盖
 集合覆盖——边覆盖问题是集合覆盖问题的一个特例：集合的元素是顶点，每个子集正好覆盖两个元素。

 注释 

 参考文献 


 .
Category:多项式时间问题