FindClique

FindClique[g]
求图 g 中最大团.

FindClique[g,n]
求含有至多 n 个顶点的团.

FindClique[g,{n}]
求恰好有 n 个顶点的团.

FindClique[g,{nmin,nmax}]
求顶点数在 之间的团.

FindClique[g,nspec,s]
求至多 s 个团.

FindClique[{g,v},]
求仅含有顶点 v 的团.

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

更多信息更多信息

  • 一个团是一组顶点的最大集合,这些顶点所对应的子图是一个完全图.
  • FindClique 返回团列表.
  • 如果没有找到团,FindClique 将返回空列表.
  • FindClique[,nspec,All] 会找到所有团.
  • 对于加权图,FindClique 给出具有最大顶点权值和的顶点集合.
  • FindClique 适用于无向图、有向图、加权图、多重图和混合图.

背景
背景

  • FindClique 求图中指定尺寸的团,以顶点列表的列表形式返回. 这里,团是使得顶点对应的子图是完全图的顶点子集. 团用于项目选择、模式匹配、金融和网络分析中。一般来说,FindClique[g,nspec,s] 求得图 g 中指定尺寸为 nspecs 个团的集合.
  • 有两个特别重要的团的类型:最大团和极大团. 要注意它们并不等价. 一个最大团是对于给定的图包含有最大可能顶点数量的团. 与此相反,一个极大团是不能通过包括多一个相邻顶点来扩展的团,这意味着它不是一个更大的团的子集. 一个最大团因此总是极大的(因为既然已经到达最大了显然它不能再扩展了),但反之则未必为真. 让术语更加混淆的是,一些作者把最大团简单称为.
  • FindClique 可以找到不同大小的极大团. FindClique 也可以找到指定大小的单个极大团,指定数量的团,或所有这样的团.
  • FindClique[g] 求得图 g 的单个最大团,FindClique[g,Length/@FindClique[g],s] 找到最多 s 个,而 FindClique[g,Length/@FindClique[g],All] 找出所有这样的团. 图 g 的最大团的数量被称为它的团数,而对于给定的图找到最大团的数量这一问题是 NP 完全的,这意味着计算可能是指数级的缓慢.
  • FindClique[g,Infinity] 求得图 g 的单个极大团,FindClique[g,Infinity,s] 能求得最多 s 个,而 FindClique[g,Infinity,All] 会求所有这样的团. 极大团在图论应用中非常重要,包括在图着色和分数图着色问题中.
  • 不一定极大的团不可以用 FindClique 直接求得,但可以通过对所有极大团的所有子集求并简单枚举出来.
  • 图的极大独立顶点集(可以使用 FindIndependentVertexSet 得到)等价于在其 GraphComplement 上的极大团. 可以用 CompleteGraphQ[g,vlist] 检验图 g 的一组顶点 vlist 是否是团(不需要它是极大的). FindKCliqueFindKClanFindKClub 得到类似团的结构,允许子图中不太完全的连接.

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

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

求一个图中的最大团:

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

显示团:

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

求所有的团:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
2010年引入
(8.0)
| 2015年更新
(10.3)
Translate this page: