Vertex Cover

定义 Definition

Vertex cover（顶点覆盖）：在图论中，指一个顶点集合，使得图中每一条边至少有一个端点在这个集合里。常见问题是求最小顶点覆盖（minimum vertex cover），即包含顶点数最少的顶点覆盖。（该术语也常出现在算法与计算复杂性中。）

发音 Pronunciation

/ˈvɝːtɛks ˈkʌvər/

例句 Examples

A vertex cover touches every edge in the graph.
顶点覆盖会“覆盖”图中的每一条边（即每条边至少有一个端点被选中）。

Finding a minimum vertex cover is NP-complete in general graphs, but it can be solved efficiently in bipartite graphs.
在一般图中求最小顶点覆盖是 NP-完全问题，但在二分图中可以高效求解。

词源 Etymology

vertex 来自拉丁语 vertex，本义与“顶点、最高点、转折点”相关；在数学与图论里引申为“图的顶点/节点”。cover 来自古法语 covrir（覆盖、遮盖）。合在一起，vertex cover 字面意思是“用顶点来覆盖（所有边）”，对应其图论定义。

相关词 Related Words

• Bipartite
• Clique
• Edge
• Graph
• Independent
• Matching
• NP-Complete
• Vertex

文学与经典作品 Literary Works

• Michael R. Garey & David S. Johnson，《Computers and Intractability: A Guide to the Theory of NP-Completeness》——将 Vertex Cover 作为经典 NP-完全问题之一系统讨论。
• **Thomas H. Cormen et al.**，《Introduction to Algorithms（CLRS）》——在图算法与复杂性相关章节中介绍顶点覆盖及其相关归约思想。
• Richard M. Karp (1972), “Reducibility Among Combinatorial Problems”——将顶点覆盖列入著名的 NP-完全问题集合与归约框架中。