VertexCoverQ

VertexCoverQ[g,vlist]
如果顶点列表 vlist 是图 g 的一个顶点覆盖,产生 True;否则,产生 False.

更多信息更多信息

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

背景
背景

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

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

基本范例  (2)基本范例  (2)

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

In[1]:=
Click for copyable input
Out[1]=

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

In[1]:=
Click for copyable input
Out[1]=
2010年引入
(8.0)
| 2014年更新
(10.0)