Minimum Vertex Cover

释义 Definition

最小顶点覆盖（图论）：在一个图 (G=(V,E)) 中，选择一个顶点集合 (C \subseteq V)，使得对每一条边 ((u,v)\in E)，至少有一个端点在 (C) 里；在所有满足条件的顶点覆盖中，顶点数最少的称为 minimum vertex cover。
（常见相关概念：vertex cover 是“顶点覆盖”，minimum 强调“规模最小”。）

发音 Pronunciation (IPA)

/ˈmɪnɪməm ˈvɜːrtɛks ˈkʌvər/

例句 Examples

We found a minimum vertex cover of size 3.
我们找到了一个大小为 3 的最小顶点覆盖。

In bipartite graphs, the minimum vertex cover size equals the maximum matching size by König’s theorem.
在二分图中，根据柯尼希定理，最小顶点覆盖的大小等于最大匹配的大小。

词源 Etymology

该术语由三部分构成：minimum（最小的）+ vertex（顶点，源自拉丁语 vertex，意为“顶点/最高点”）+ cover（覆盖）。在图论里，“cover（覆盖）”表示用某个集合去“覆盖/命中”所有目标对象；这里指用顶点集合去“覆盖”所有边（每条边至少被一个端点“命中”）。这一表述在20世纪图论与组合优化的发展中逐渐固定下来，并在复杂性理论中成为经典问题之一（最小顶点覆盖为著名的 NP-完全问题）。

相关词 Related Words

• Vertex
• Edge
• Graph
• Vertex Cover
• Independent Set
• Matching
• Bipartite Graph
• König’s Theorem
• NP-Complete
• Approximation Algorithm

文学与典籍 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）中在近似算法与经典NP问题讨论里常提到 vertex cover / minimum vertex cover。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）将 Vertex Cover 作为著名的 NP-完全问题条目之一，常以“最小顶点覆盖”的形式出现。
• Graph Theory（Reinhard Diestel）与 Introduction to Graph Theory（Douglas B. West）等图论教材中，在顶点覆盖、独立集、匹配等章节常出现该术语及其性质。