7,129
个编辑
更改
跳到导航
跳到搜索
第5行：
第5行： − + − + − + − + − The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4. 第19行：
第18行： − + − − A '''clique''', ''C'', in an [[undirected graph]] {{nowrap|''G'' {{=}} (''V'', ''E'')}} is a subset of the [[Vertex (graph theory)|vertices]], {{nowrap|''C'' ⊆ ''V''}}, such that every two distinct vertices are adjacent. This is equivalent to the condition that the [[induced subgraph]] of ''G'' induced by ''C'' is a [[complete graph]]. In some cases, the term clique may also refer to the subgraph directly. − − A clique, C, in an undirected graph (V, E)}} is a subset of the vertices, , such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly. − 第40行：
第34行： − + 第52行：
第46行： − + 第224行：
第218行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − [[Category:图论对象]] + − 此词条由Jie初步翻译，由Flipped审校。+
无编辑摘要
[[文件:VR complex.svg|缩略图|
[[文件:VR complex.svg|缩略图|
• 23 × 1-vertex cliques (the vertices), 23个单顶点团（顶点）
• 23个单顶点团（顶点）
• 42 × 2-vertex cliques (the edges), 42个双顶点团（边）
• 42个双顶点团（边）
• 19 × 3-vertex cliques (light and dark blue triangles), 19个三顶点团（浅色和深色的三角形）
• 19个三顶点团（浅色和深色的三角形）
• 2 × 4-vertex cliques (dark blue areas).2个四顶点团（深色区域）
• 2个四顶点团（深色区域）
11个浅蓝色三角形（三顶点团）为极大团。2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
11个浅蓝色三角形（三顶点团）为极大团。2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
]]
]]
== Definitions 定义 ==
== 定义 ==
在一个无向图''G =（V，E）''中，团''C''是顶点''V''的子集，记作：''C⊆V''，使得每两个不同的顶点相邻。这可以视作，由''C''引导出的“G”内的导出图是完全图的条件。在某些情况下，“团”这一术语也可以直接指代子图。
在一个无向图''G =（V，E）''中，团''C''是顶点''V''的子集，记作：''C⊆V''，使得每两个不同的顶点相邻。这可以视作，由''C''引导出的“G”内的导出图是完全图的条件。在某些情况下，“团”这一术语也可以直接指代子图。
一个图的''' 最大团横贯集Maximum clique transversal'''是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
一个图的''' 最大团横贯集 Maximum clique transversal'''是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
有关团的数学结论包括以下内容。
有关团的数学结论包括以下内容。
* ''' 托兰定理 Turán's theorem '''在''' 稠密图Dense graph'''中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过<math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math>个边的图形都必然含一个三顶点团。
* ''' 托兰定理 Turán's theorem '''在''' 稠密图 Dense graph'''中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过<math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math>个边的图形都必然含一个三顶点团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3<sup>''n''</sup>个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3<sup>''n''</sup>个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
{{refend}}
{{refend}}
==编辑推荐==
===书籍推荐===
====《图论导论》====
Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。
<br/>
====[https://vdisk.weibo.com/s/dDPmAoC9qB694 《图论及其应用》]====
该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。
</br>
===集智文章推荐===
*集智俱乐部：[https://swarma.org/?p=1113 种群结构如何影响自然选择？ | 图论对进化生物学的启发]
*集智斑图：[https://pattern.swarma.org/paper?id=d25fb568-16f8-11ea-91b3-0242ac1a0005 Graph theory in the information age 信息时代的图论]
*集智斑图：[https://pattern.swarma.org/paper?id=24dc7004-2808-11ea-a1e5-0242ac1a0007 Graph Theory and Metro Traffic Modelling 图论与地铁交通模型]
</br>
===课程推荐===
====[https://campus.swarma.org/course/1745 漫谈图论的起源、发展与应用]====
网络科学研究中许多网络包含数千个甚至数百万个节点和链接。在研究小网络的基础上，还需要走的更远。对于具有很多节点和连边的网络，过于复杂，目测的方式对于理解和认识这类网络不再适用。需要适用网络科学的工具来刻画网络的拓扑，例如：度、度分布、邻接矩阵、加权网络、二分网络、路径、距离、连通性、集聚系数等。
该课程介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。随后的章节将系统地研究这些网络性质，深入理解这些网络性质在认识复杂系统方面发挥的重要作用。
====[https://campus.swarma.org/course/1790 书籍领读：图论]====
本课程中，将讲解巴拉巴西网络科学书籍第一章图论。
<br/>
----
本中文词条Jie初步翻译，由Flipped审校，[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:图论对象]]