团（图论）

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索


*23个单顶点团（顶点）
*42个双顶点团（边）
*19个三顶点团（浅色和深色的三角形）
*2个四顶点团（深色区域）
*11个浅蓝色三角形（三顶点团）为极大团
*2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。

在图论的数学领域中，团 Clique是无向图中顶点的子集，使得一个团中每两个不同的顶点必定相邻。也就是说，其导出子图是完全图。团是图论的基本概念之一，可用于图形的构建和解决许多其他数学问题。而且，在计算机科学领域中也经常会涉及到团的研究：比如在一个给定规模的图中寻找团的存在就是一个NP-完全问题。尽管我们已经明确知道这个问题很难得以解决，但仍然有许多学者在研究用于寻找团的算法。


对完全子图的研究至少可以追溯到拉姆齐定理 Ramsey's theorem中的图论重组，由Erdős＆Szekeres（1935）在论文《几何组合问题 A combinatorial problem in geometry》提出的。但实际上“团”一词是来自Luce＆Perry（1949）的论文《群结构矩阵分析的一种方法 A method of matrix analysis of group structure》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。


定义

在一个无向图G =（V，E）中，团C是顶点V的子集，记作：C⊆V，使得每两个不同的顶点相邻。这可以视作，由C引导出的“G”内的导出图是完全图的条件。在某些情况下，“团”这一术语也可以直接指代子图。


极大团 Maximal clique也是一个团，但是不能通过合并更多的相邻节点而进行扩张，换句话说，该团不可能被更大团的顶点集合所包含。有些学者将“极大团”定义为“团”，用其他完全子团的术语来重新定义“非极大团”。


图G中同样存在一个最大团 Maximum clique，使得其不存在更多顶点。另外，图G的团数ω（G）是该图最大团的顶点数。


图G的交叉数 Intersection number是该图中同时能覆盖所有连边的最少团数。


图G的团覆盖数 Clique cover number指的是能覆盖图G中所有顶点集V的最少团数。


一个图的 最大团横贯集 Maximum clique transversal是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。


作为团的对立面，独立集 Independent set是指图中两两互相不相邻的顶点集合。因此，每一个团都对应于补图中的独立集。集团覆盖问题涉及到寻找尽可能少的团，其中包括图中的每个顶点。


二元团 biclique是团的相关概念，指的是一个完全二分图。该图的二分维度指的是覆盖该图所有连边所需的最少二元团数。


数学运算

有关团的数学结论包括以下内容。

  • 托兰定理 Turán's theorem 在 稠密图 Dense graph中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过[math]\displaystyle{ \scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil }[/math]个边的图形都必然含一个三顶点团。
  • 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
  • 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3n个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
  • 关于Hadwiger的猜想，目前尚未得到证实，其认为图中最大的团子式的大小（即Hadwiger数）与其色数相关。
  • Erdős–Faber–Lovász猜想是另一个未经证实的陈述，同样认为图的着色与团相关。


由"团"的特性来定义和区分几种重要的"图"类别：


  • 聚类图 Cluster graph是图的一种特例，其连接的组成部分是团。
  • 框图 Block graph是图的一种特例，其双连通的部分是团。
  • 弦图 Chordal graph是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
  • 余图 Cograph是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
  • 区间图 Interval graph是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
  • 线图 Line graph是图的一种特例，其连边可以被边不相交的团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
  • 完美图 Perfect graph是图的一种特例，其导出子图的色数等于此导出子图的团数。
  • 分裂图 Split graph是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
  • 三角形无关图 Triangle-free graph是图的一种特例，除了顶点和连边之外，该图不含任何团。


此外，还有许多其他数学结构与图论的"团"有关。它们包括，


  • 图G的团复形 Clique complex属于抽象复形 Abstract simplicial complex，其中图G的每个团都为单纯形。
  • 单纯形图 Simplex graph可记为无向图κ（G），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。它是中线图的一个示例，并且与图中团的中位数相关联：三个团A，B和C的中位团m（A，B，C），其顶点至少属于团A，B和C中的两个。


  • 团相加 Clique-sum指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
  • 团宽度 Clique-width是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。即通过不相交的并集构建图形所需的不同顶点标签的最小数量，通过以下操作建立：
  1. 将两个已标记的图拆开，使其不相交；
  2. 重新标记；
  3. 根据给定的标记，连接所有成对顶点。


团宽度为1的图就是团的不相交并集。

  • 图的交叉数Intersection number指的是能覆盖图所有连边所需的最小团数。
  • 图G的团图 Clique graph指的是该图的极大团的交叉图。主要为了展示图G的团结构。


从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。


计算机科学

在计算机科学中，团问题指的是在给定图中查找最大团或所有团的计算问题。它是是Karp提出的21个NP-完全问题之一。它也是固定参数难求解问题，甚至难以获得近似值。尽管如此，目前专业人士已经开发了诸多用于计算团的算法，包括可以在指数时间内求解的例如Bron–Kerbosch算法，以及在多项式时间内专门求解图族（例如平面图或完美图）这类问题的算法。


应用

“团clique”一词在图形理论上的使用，来源于Luce＆Perry（1949）的研究《A method of matrix analysis of group structure》，他们通过完全子图对社交网络中的集团（彼此认识的人群）进行建模。之后Festinger（1949）在论文《使用矩阵代数的社会图分析 The analysis of sociograms using matrix algebra》中以较少的术语进行了相同的定义。这两部作品都通过使用矩阵处理社交网络中的团问题。之后，Alba（1973），Peay（1974）和Doreian＆Woodard（1994）以图理论为基础对社交团体继续进行了图形化建模。


在生物信息学领域，诸多不同问题都已经通过“团”来实现建模。例如，Ben-Dor，Shamir和Yakhini（1999）对基因表达数据的聚类问题进行了建模，通过将数据描述的图转换为含有不相交团的图，并在转变过程中找寻最小改变量。另外，Tanay，Sharan＆Shamir（2002）讨论了一个类似的表达数据的双聚类问题，在该问题中，群集被描述为“团”。Sugihara（1984）使用“团”对食物网中的生态位进行建模。Day＆Sankoff（1986）将推论进化树的问题描述为在具有该物种顶点特征的图形中找到最大团的问题之一，如果存在一个物种能将这两个特征完美结合，则两个顶点共享一条边。Samudrala＆Moult（1998）将蛋白质结构预测模型化为， 在顶点表示蛋白质亚基位置的图中发现团簇的问题。通过在蛋白质-蛋白质相互作用网络中寻找群体，Spirin＆Mirny（2003）发现了彼此紧密相互作用的蛋白质簇，并且与簇外部的蛋白质几乎没有相互作用。功率图分析是一种通过在这些网络中查找团簇和相关结构来简化复杂生物网络的方法。


在电气工程中，Prihar（1956）使用团来分析通信网络，Paull＆Unger（1959）使用它们来设计有效的电路，以计算部分指定的布尔函数。团也已用于自动测试模式生成：不兼容图中可能出现故障的大团为测试集的大小提供了下限。Cong＆Smith（1993）描述了团在划分电子电路分层中的应用。


在化学上，Rhodes等学者（2003年）使用团来描述化学数据库中与目标结构具有高度相似性的化学物质。Kuhl，Crippen＆Friesen（1983）使用团对两种化学物质相互结合的位置进行建模。


参考文献

  • Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826.
  • Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188.
  • Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, MR 1905299.
  • Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
  • Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.
  • Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 978-1581130089.
  • Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103.
  • Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105.
  • Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions", IRE Transactions on Electronic Computers, EC-8 (3): 356–367, doi:10.1109/TEC.1959.5222697.
  • Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
  • Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.), Population Biology, Proc. Symp. Appl. Math., vol. 30, pp. 83–101.
  • Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in magyar), 48: 436–452


编辑推荐

书籍推荐

《图论导论》

Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。


《图论及其应用》

该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。


集智文章推荐


课程推荐

漫谈图论的起源、发展与应用

网络科学研究中许多网络包含数千个甚至数百万个节点和链接。在研究小网络的基础上，还需要走的更远。对于具有很多节点和连边的网络，过于复杂，目测的方式对于理解和认识这类网络不再适用。需要适用网络科学的工具来刻画网络的拓扑，例如：度、度分布、邻接矩阵、加权网络、二分网络、路径、距离、连通性、集聚系数等。

该课程介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。随后的章节将系统地研究这些网络性质，深入理解这些网络性质在认识复杂系统方面发挥的重要作用。


书籍领读：图论

本课程中，将讲解巴拉巴西网络科学书籍第一章图论。



本中文词条Jie初步翻译，由Flipped审校，薄荷编辑，如有问题，欢迎在讨论页面留言。


本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=团（图论）&oldid=28114”