WOLFRAM

Wolfram 语言与系统参考资料中心

VertexCoverQ[g,vlist]

如果顶点列表 vlist 是图 g 的一个顶点覆盖，产生 True；否则，产生 False.

更多信息
Details and Options Details and Options
背景
范例  
基本范例  
范围  
应用  
属性和关系  
参见
相关指南
历史
按以下格式引用：

VertexCoverQ

VertexCoverQ[g,vlist]

如果顶点列表 vlist 是图 g 的一个顶点覆盖，产生 True；否则，产生 False.

更多信息

  • 顶点覆盖是与每条边相关联的顶点集合.
  • VertexCoverQ 可用于无向图、有向图、多图和混合图.

背景

  • VertexCoverQ 检验指定的顶点集合是否形成了所给图的顶点覆盖，其中，顶点覆盖指的是一个满足下述条件的顶点集合：图的每条边都和集合中的某些顶点相关. 如果集合是顶点覆盖，VertexCoverQ 返回 True，否则，返回 False.
  • 一个图的全部顶点覆盖还是一个顶点覆盖（大小是最大的）. 一个图的可能的所含顶点数量最少的顶点覆盖被称为最小顶点覆盖，它的大小被称为顶点覆盖数.
  • 顶点覆盖与独立的顶点集合（集合中没有两个顶点属于同一条边）有密切的关系. 具体来讲，当且仅当一个顶点集合的补集形成一个独立的顶点集合时，该集合才是一个顶点覆盖. 因此，一个图中顶点覆盖的数目和独立顶点集合的数目是一样的.
  • FindVertexCover 可用来找出单个的最小顶点覆盖或单个的任意大小的顶点覆盖，但无法给出所有的顶点覆盖. 一个简单的找出所有顶点覆盖的的方法是对图的顶点的所有子集应用 VertexCoverQ. EdgeCoverQ 能对图的边覆盖进行和 VertexCoverQ 类似的检验. FindIndependentVertexSet 可用来找出图的一个或更多的最大独立顶点集合（它们的每一个补集都是一个顶点覆盖）.

范例

打开所有单元 关闭所有单元

基本范例  (2)

检验顶点集合是否是图中的一个顶点覆盖：

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

不是所有顶点集合都是图中的顶点覆盖：

Wolfram Language code: VertexCoverQ[[image], {1, 4}]

范围  (6)

检验无向图：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

有向图：

Wolfram Language code: VertexCoverQ[[image], {2, 3, 6}]

多图：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

混合图：

Wolfram Language code: VertexCoverQ[[image], {1, 4, 6}]

对于非图表达式，VertexCoverQ 给出 False：

Wolfram Language code: VertexCoverQ[x, {1, 3}]

VertexCoverQ 作用于大规模图：

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: VertexCoverQ[g, {1, 2}]//Timing

应用  (2)

列举圈图中的所有顶点覆盖：

Wolfram Language code: g = CycleGraph[4, VertexSize -> Small]

列举顶点的所有子集，并且选出其中的顶点覆盖：

Wolfram Language code: Subsets[VertexList[g]]
Wolfram Language code: vcl = Select[%, VertexCoverQ[g, #]&]

突出显示顶点覆盖：

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

对一个 Petersen 图，列举出所有的最小的顶点覆盖：

Wolfram Language code: g = PetersenGraph[5, 2, VertexSize -> Medium]

求最小顶点覆盖的大小：

Wolfram Language code: FindVertexCover[g]
Wolfram Language code: n = Length[%]

列举所有的最小顶点覆盖：

Wolfram Language code: vcl = Select[Subsets[VertexList[g], {6}], VertexCoverQ[g, #]&]

突出显示所有的最小的顶点覆盖：

Wolfram Language code: Table[HighlightGraph[g, h], {h, vcl}]

属性和关系  (7)

一个图的 VertexList 是一个顶点覆盖（通常不是最小顶点覆盖）：

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, VertexList[%]]

可以使用 FindVertexCover 求最小顶点覆盖：

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: VertexCoverQ[%, FindVertexCover[%]]

当且仅当一个顶点集合的补集是一个独立集时，该集合是一个顶点覆盖：

Wolfram Language code: g = GridGraph[{2, 3}]
Wolfram Language code: vc = FindVertexCover[g]

检查顶点的补集是否是独立的：

Wolfram Language code: IndependentVertexSetQ[g, Complement[VertexList[g], vc]]

顶点覆盖和最大独立集的总大小等于顶点数：

Wolfram Language code: g = WheelGraph[8]
Wolfram Language code: Length[FindVertexCover[g]] + Length[First[FindIndependentVertexSet[g]]] == VertexCount[g]

GraphComplement 中的顶点覆盖的补集是原图中的一个团：

Wolfram Language code: g = GridGraph[{2, 3}]

使用相同的嵌入方法，计算补集：

Wolfram Language code: h = GraphComplement[g, VertexCoordinates -> GraphEmbedding[g]]
Wolfram Language code: FindVertexCover[h]

它的补集是一个团：

Wolfram Language code: Complement[VertexList[g], FindVertexCover[h]]
Wolfram Language code: Subgraph[g, %]
Wolfram Language code: CompleteGraphQ[%]

完全二分图 具有大小为 的顶点覆盖：

Wolfram Language code: CompleteGraph[{2, 4}]
Wolfram Language code: Length[FindVertexCover[%]] == Min[2, 4]

一个二分图中的最大独立边集具有和最小顶点覆盖相同的大小：

Wolfram Language code: g = CycleGraph[6]
Wolfram Language code: BipartiteGraphQ[g]
Wolfram Language code: Length[FindVertexCover[g]] == Length[FindIndependentEdgeSet[g]]
Wolfram Research (2010)，VertexCoverQ，Wolfram 语言函数，https://reference.wolfram.com/language/ref/VertexCoverQ.html （更新于 2014 年）.

文本

Wolfram Research (2010)，VertexCoverQ，Wolfram 语言函数，https://reference.wolfram.com/language/ref/VertexCoverQ.html （更新于 2014 年）.

CMS

Wolfram 语言. 2010. "VertexCoverQ." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2014. https://reference.wolfram.com/language/ref/VertexCoverQ.html.

APA

Wolfram 语言. (2010). VertexCoverQ. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/VertexCoverQ.html 年

BibTeX

@misc{reference.wolfram_2026_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 01-November-2026]}

BibLaTeX

@online{reference.wolfram_2026_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 01-November-2026]}