边覆盖

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

定义

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

 

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

 

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

例子

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

算法

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

 

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

参见

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

注释

  1. ^ 1.0 1.1 Garey & Johnson (1979), 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.
  2. ^ Lawler, Eugene L., Combinatorial optimization: networks and matroids, Dover Publications: 222–223, 2001 [2022-05-11], ISBN 978-0-486-41453-9, （原始内容存档于2022-05-11） .

参考文献

  • Weisstein, Eric W. (编). Edge Cover. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）. 
  • Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5 .