FindIndependentVertexSet

FindIndependentVertexSet[g]
求图 g 的具有最大顶点数的独立顶点集.

FindIndependentVertexSet[g,n]
求至多有 n 个顶点的独立顶点集.

FindIndependentVertexSet[g,{n}]
求恰好具有 n 个顶点的独立顶点集.

FindIndependentVertexSet[g,{nmin,nmax}]
求所含顶点数在 之间的独立顶点集.

FindIndependentVertexSet[g,nspec,s]
求至多 s 个独立顶点集.

FindIndependentVertexSet[{g,v},]
求仅包含顶点 v 的独立集.

FindIndependentVertexSet[{vw,},]
使用规则 指定图 g.

更多信息更多信息

背景
背景

  • FindIndependentVertexSet 会找出图中的一个或更多的极大独立顶点集,以顶点列表的列表形式返回. 这里,独立顶点集是一个顶点集合,此集合中任意两个顶点之间都没有边相连. 独立顶点集在金融、编码理论、地图标注、模式识别、社交网络、分子生物学和调度方面都有应用.
  • 有两种特别重要的独立顶点集:最大独立集和极大独立集. 要注意这两种并不等价. 最大独立顶点集是包含给定图的最多顶点的独立集. 与之相反,极大独立顶点集是无法再添加相邻顶点的顶点集,这意味着它不是更大的独立顶点集的子集. 最大独立顶点集因此总是极大的,反之则未必成立.
  • FindIndependentVertexSet 能找到不同大小的极大独立顶点集. FindIndependentVertexSet 也能找到指定大小的单个极大独立顶点集,指定数量的极大独立顶点集,或所有这样的集合.
  • FindIndependentVertexSet[g] 能找出图 g 的单个最大独立顶点集,FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],s] 能找出最多有 s 个顶点的,而 FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All] 能找出全部这样的集合. 图 g 的最大独立顶点集的大小被称为其(顶点)独立数. 找出给定图的最大独立顶点集(以及由此可得的独立数)这一问题是 NP 完全的,这意味着计算会极其慢.
  • FindIndependentVertexSet[g,Infinity] 能找出图 g 的单个极大独立顶点集,FindIndependentVertexSet[g,Infinity,s] 能找出最多 s 个顶点集,而 FindIndependentVertexSet[g,Infinity,All] 能找出全部这样的集合.
  • 不一定极大的独立顶点集不能用 FindIndependentVertexSet 直接求得,但可通过对所有极大独立顶点集的所有子集求并集以简单枚举出来.
  • 可以用 IndependentVertexSetQ 检测一个顶点集是不是独立的(不需要它还是极大的). 独立顶点集对应的是顶点覆盖的补集(和 FindVertexCover 比较). 极大独立顶点集等价于 GraphComplement 上的极大团(和 FindClique 比较). FindIndependentEdgeSet 将与 FindIndependentVertexSet 相同的概念应用到边上,得到的独立边集也被称为匹配.
2010年引入
(8.0)
| 2015年更新
(10.3)
Translate this page: