查看“︁覆盖 (图论)”︁的源代码

[[File:Vertex covers.svg|thumb|左上图<span style="color:red">红色[[顶点 (图论)|顶点]]</span>覆盖了<span style="color:green">四条[[邊 (圖論)|边]]</span>（标记为绿色），剩余两条黑边未覆盖。<br/>
右上图<span style="color:red">红色[[顶点 (图论)|顶点]]</span>覆盖了<span style="color:green">三条[[邊 (圖論)|边]]</span>，剩余三条边未覆盖。<br/>
下图用两个<span style="color:red">红色顶点</span>完成了<span style="color:green">所有边</span>的覆盖。
]]

图的'''覆盖'''是一個[[顶点 (图论)|顶点]]的集合，使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为'''顶点覆盖问题'''（{{tsl|en|Vertex cover}}），它是一个[[NP完全]]问题。

顶点覆盖和边覆盖分别与[[独立集合]]和[[匹配 (图论)|匹配问题]]有关。

==定义==

图''G''的'''[[顶点 (图论)|顶点]]覆盖'''是一个顶点集合''V''，使得''G''中的每一条边都接触''V''中的至少一个顶点。我们称集合''V''覆盖了''G''的边。最小顶点覆盖是用最少的顶点来覆盖所有的边。'''顶点覆盖数'''<math>\tau</math>是最小顶点覆盖的大小。

相应地，图''G''的'''边覆盖'''是一个边集合''E''，使得''G''中的每一个顶点都接触''E''中的至少一条边。

如果只说覆盖，则通常是指顶点覆盖，而不是边覆盖。

==例子==
* 任何一个图的[[顶点 (图论)|顶点]]集合都覆盖了它的边集合。如果图中不含有零度顶点，则反过来也成立。
* [[完全二部图]]''K''<sub>''m'',''n''</sub>的顶点覆盖数为min(''m'', ''n'')，边覆盖数为max(''m'', ''n'')。

==性质==
* 图的[[顶点 (图论)|顶点]]数目等于顶点覆盖数与最大独立集合的大小之和（Gallai 1959）。

==参考文献==
* Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. '''2''', 133-138, 1959.

[[Category:图论]]