更改

添加1,374字节 、 2021年12月30日 (四) 20:34
无编辑摘要
第5行: 第5行:     
[[文件: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个四顶点团(深色区域)
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.
   
11个浅蓝色三角形(三顶点团)为极大团。2个深蓝色的四顶点团既是最大团也是极大团,该图的团数是4。
 
11个浅蓝色三角形(三顶点团)为极大团。2个深蓝色的四顶点团既是最大团也是极大团,该图的团数是4。
 
]]
 
]]
第19行: 第18行:       −
== Definitions 定义 ==
+
== 定义 ==
 
  −
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.
  −
 
   
在一个无向图''G =(V,E)''中,团''C''是顶点''V''的子集,记作:''C⊆V'',使得每两个不同的顶点相邻。这可以视作,由''C''引导出的“G”内的导出图是完全图的条件。在某些情况下,“团”这一术语也可以直接指代子图。
 
在一个无向图''G =(V,E)''中,团''C''是顶点''V''的子集,记作:''C⊆V'',使得每两个不同的顶点相邻。这可以视作,由''C''引导出的“G”内的导出图是完全图的条件。在某些情况下,“团”这一术语也可以直接指代子图。
   第40行: 第34行:       −
一个图的''' 最大团横贯集Maximum clique transversal'''是其顶点的子集,其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
+
一个图的''' 最大团横贯集 Maximum clique transversal'''是其顶点的子集,其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
      第52行: 第46行:  
有关团的数学结论包括以下内容。
 
有关团的数学结论包括以下内容。
   −
* ''' 托兰定理 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,...,该图相当于托兰图的特例,是托兰定理中的极端情况。
第224行: 第218行:  
{{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审校,[[用户:薄荷|薄荷]]编辑,如有问题,欢迎在讨论页面留言。
      −
[[Category:图论对象]]
      +
'''本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。'''
   −
此词条由Jie初步翻译,由Flipped审校。
+
[[Category:图论对象]]
7,129

个编辑