FindClique

FindClique[g]

求图 g 中最大团.

FindClique[g,n]

求含有至多 n 个顶点的团.

FindClique[g,{n}]

求恰好有 n 个顶点的团.

FindClique[g,{nmin,nmax}]

求顶点数在 nmin 和 nmax 之间的团.

FindClique[g,nspec,s]

求至多 s 个团.

FindClique[{g,v},…]

求仅含有顶点 v 的团.

FindClique[{vw,…},…]

用规则 vw 指定图 g.

更多信息

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

背景

  • FindClique 求图中指定尺寸的团，以顶点列表的列表形式返回. 这里，团是使得顶点对应的子图是完全图的顶点子集. 团用于项目选择、模式匹配、金融和网络分析中。一般来说，FindClique[g,nspec,s] 求得图 g 中指定尺寸为 nspec 的 s 个团的集合.
  • 有两个特别重要的团的类型：最大团和极大团. 要注意它们并不等价. 一个最大团是对于给定的图包含有最大可能顶点数量的团. 与此相反，一个极大团是不能通过包括多一个相邻顶点来扩展的团，这意味着它不是一个更大的团的子集. 一个最大团因此总是极大的（因为既然已经到达最大了显然它不能再扩展了），但反之则未必为真. 让术语更加混淆的是，一些作者把最大团简单称为“团”.
  • 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 是否是团（不需要它是极大的）. FindKClique、FindKClan 和 FindKClub 得到类似团的结构，允许子图中不太完全的连接.

范例

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

基本范例  (2)

求一个图中的最大团：

显示团：

求所有的团：

范围  (14)

规范  (8)

FindClique 可用于无向图：

有向图：

加权图：

多重图：

混合图：

求最大团：

使用规则来指定图：

FindClique 适用于大型图：

枚举  (6)

恰好包含3个顶点的团：

至多包含2个顶点的团：

顶点数在3到5之间的团：

包含给定顶点的最大团：

求图中所有的团：

如果没有团则 FindClique 给出空列表：

应用  (5)

突出显示图中所有的团：

求包含最亲近亲属，包括父母、兄弟姐妹和孩子的网络中的最大直系家庭成员：

突出显示团：

一个书籍网络由亚马逊上相同购买者组成. 求经常与 The Clinton Wars 一起购买的书籍的最大集合：

求1998年东非大使馆袭击网络中的恐怖分子单元：

显示合作的恐怖分子单元：

求孤立 Dar es Salaam 袭击单元的外部联系人：

求收益同步改变的道琼斯工业指数平均值成员：

首先计算从今年初开始收益相关性：

构建一个图，其中的边连接的是相关系数高于选定的 的股票：

倾向于同步改变的股票的最大集合：

显示累积收益图线：

属性和关系  (8)

一个团是生成一个完全子图的最大顶点集：

{1,2,3} 和 {1,2,3,4} 可以形成完全子图，但不是最大的：

由团导出的子图是完全图：

由团导出的子图是完全图：

一个图的团是它的补图的独立顶点集：

一个图的团的顶点的补集是它补图的顶点覆盖：

完全图的最大团含有它所有的顶点：

一个完全 部图具有大小为 的最大团：

大小为 的最大团包括在一个 核分量中：

2 核心分量：

当 时，所有团是 -团、-宗派、-club 和 -丛图：

相反地，所有的 1 团、1 宗派、1 club 和 1 丛都是团：

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

文本

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

CMS

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

APA

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

BibTeX

@misc{reference.wolfram_2024_findclique, author="Wolfram Research", title="{FindClique}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindClique.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findclique, organization={Wolfram Research}, title={FindClique}, year={2015}, url={https://reference.wolfram.com/language/ref/FindClique.html}, note=[Accessed: 18-November-2024 ]}