WOLFRAM

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

VertexCoverQ
✖
VertexCoverQ

✖
VertexCoverQ[g,vlist]

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

更多信息

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

背景

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

范例

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

基本范例  (2)常见实例总结

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-8qm2ha
Out[1]=1

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-khmgs5
Out[1]=1

范围  (6)标准用法实例范围调查

检验无向图：

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-c4jban
Out[1]=1

有向图：

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-d92a8t
Out[1]=1

多图：

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-15kl6n
Out[1]=1

混合图：

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-czvddh
Out[1]=1

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-3l2bwe
Out[1]=1

VertexCoverQ 作用于大规模图：

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-hlltv6
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-hrht0p
Out[2]=2

应用  (2)用该函数可以解决的问题范例

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-k7ld2c
Out[1]=1

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

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-hyw7qp
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-htjso
Out[3]=3

突出显示顶点覆盖：

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-b9l00i
Out[4]=4

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-hiv33l
Out[1]=1

求最小顶点覆盖的大小：

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-zjd84
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-mqn8zl
Out[3]=3

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

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-c7l5n7
Out[4]=4

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

In[5]:=5
✖
https://wolfram.com/xid/0dc3e0saikzn-nuwksv
Out[5]=5

属性和关系  (7)函数的属性及与其他函数的关联

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-cou4t4
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-jhwg5r
Out[2]=2

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-fds0n0
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-habyrc
Out[2]=2

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-8asoh
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-cj29j9
Out[2]=2

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

In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-jg28gl
Out[3]=3

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-dme9ws
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-grp108
Out[2]=2

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-d0kb5r
Out[1]=1

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

In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-eblt1f
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-d1c34
Out[3]=3

它的补集是一个团：

In[4]:=4
✖
https://wolfram.com/xid/0dc3e0saikzn-ed5oub
Out[4]=4
In[5]:=5
✖
https://wolfram.com/xid/0dc3e0saikzn-qfwrfz
Out[5]=5
In[6]:=6
✖
https://wolfram.com/xid/0dc3e0saikzn-fbxu48
Out[6]=6

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-ex4zx8
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-idoe5c
Out[2]=2

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

In[1]:=1
✖
https://wolfram.com/xid/0dc3e0saikzn-ecgbva
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0dc3e0saikzn-bicsi8
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dc3e0saikzn-hcbva
Out[3]=3
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 年）.

文本

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.

✖
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 年

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

BibTeX

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

✖
@misc{reference.wolfram_2025_vertexcoverq, author="Wolfram Research", title="{VertexCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/VertexCoverQ.html}", note=[Accessed: 07-May-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 07-May-2025 ]}

✖
@online{reference.wolfram_2025_vertexcoverq, organization={Wolfram Research}, title={VertexCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/VertexCoverQ.html}, note=[Accessed: 07-May-2025 ]}