边覆盖

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

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

:

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

:

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

例子

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

算法
通过找到一个最大基数匹配并贪婪地扩展它直到覆盖所有顶点，可以在多项式时间内找到最小的边缘覆盖。 在下图中，最大基数匹配用红色标记；为覆盖不匹配节点而添加的额外边用蓝色标记。 （右图的最大基数匹配是完美匹配；因此它已经覆盖了所有顶点，不再需要额外的边去覆盖。 )

:

另一方面来说，寻找最小点覆盖的相关问题是一个NP困难问题。

参见

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

注释
参考文献
*

• .