查看“︁边覆盖”︁的源代码

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

{{覆盖-包装问题对}}

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

:[[File:Edge-cover.svg]]

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

:[[File:Minimum-edge-cover.svg]]

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

=== 例子 ===

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

== 算法 ==
通过找到一个[[最大匹配|最大基数匹配]]并贪婪地扩展它直到覆盖所有顶点，可以在[[多項式時間|多项式时间]]内找到最小的边缘覆盖。 <ref name="gt79">{{Harvard citation text|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.</ref> <ref>{{Citation|title=Combinatorial optimization: networks and matroids|first=Eugene L.|last=Lawler|publisher=Dover Publications|year=2001|isbn=978-0-486-41453-9|pages=222–223|url=https://books.google.com/books?id=m4MvtFenVjEC&pg=PA222|accessdate=2022-05-11|archive-date=2022-05-11|archive-url=https://web.archive.org/web/20220511155946/https://books.google.com/books?id=m4MvtFenVjEC&pg=PA222}}.</ref>在下图中，最大基数匹配用红色标记；为覆盖不匹配节点而添加的额外边用蓝色标记。 （右图的最大基数匹配是[[完美匹配]]；因此它已经覆盖了所有顶点，不再需要额外的边去覆盖。 )

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

另一方面来说，寻找最小[[頂點覆蓋|点覆盖]]的相关问题是一个[[NP困难]]问题。 <ref name="gt79">{{Harvard citation text|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.</ref>

== 参见 ==

* [[頂點覆蓋|顶点覆盖]]
* [[集合覆盖问题|集合覆盖]]——边覆盖问题是集合覆盖问题的一个特例：''集合''的元素是顶点，每个''子集''正好覆盖两个元素。

== 注释 ==
{{Reflist}}

== 参考文献 ==

* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>{{cite mathworld|urlname=EdgeCover|title=Edge Cover}}
* {{Citation|last=Garey|first=Michael R.|authorlink1=Michael R. Garey|last2=Johnson|first2=David S.|authorlink2=David S. Johnson|year=1979|title=[[Computers and Intractability: A Guide to the Theory of NP-Completeness]]|publisher=W.H. Freeman|isbn=0-7167-1045-5}}.
[[Category:多项式时间问题]]