边覆盖

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

定义

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

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

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

例子

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

算法

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

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

参见

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

参考文献

• Template:Cite mathworld
• Template:Citation.