961
个编辑
更改
跳到导航
跳到搜索
第95行：
第95行： − 有关“团”的数学结论包括以下内容。+ 第105行：
第105行： − + − + 第115行：
第115行： − 由“团”的特性来定义和区分“图”类别的相关描述：+ 第129行：
第129行： − + − + − + − + − + − + − + − + − + 第143行：
第143行： − 此外，还有许多其他数学结构与图论的团有关。它们包括，+ 第153行：
第153行： − + − + − + − + − + − + − * 从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。
→Mathematics 数学运算
Mathematical results concerning cliques include the following.
Mathematical results concerning cliques include the following.
Mathematical results concerning cliques include the following.
Mathematical results concerning cliques include the following.
有关团的数学结论包括以下内容。
*The [[Erdős–Faber–Lovász conjecture]] is another unproven statement relating graph coloring to cliques.
*The [[Erdős–Faber–Lovász conjecture]] is another unproven statement relating graph coloring to cliques.
* 托兰定理在稠密图中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过个边的图形都必然含一个三顶点团。
* 托兰定理在'''<font color="#ff8000"> 稠密图Dense graph</font>'''中给出了团大小的下界。如果一个图具有足够多的边，则它必然含有较大的团。例如，每个具有n个顶点且超过个边的图形都必然含一个三顶点团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* '''<font color="#ff8000"> 拉姆齐Ramsey's theorem</font>'''定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3n个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3n个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* 关于Hadwiger的猜想，目前尚未得到证实，其认为图中最大的团子式的大小（即Hadwiger数）与其色数相关。
* 关于Hadwiger的猜想，目前尚未得到证实，其认为图中最大的团子式的大小（即Hadwiger数）与其色数相关。
Several important classes of graphs may be defined or characterized by their cliques:
Several important classes of graphs may be defined or characterized by their cliques:
Several important classes of graphs may be defined or characterized by their cliques:
Several important classes of graphs may be defined or characterized by their cliques:
由"团"的特性来定义和区分"图"类别的相关描述：
*A [[triangle-free graph]] is a graph that has no cliques other than its vertices and edges.
*A [[triangle-free graph]] is a graph that has no cliques other than its vertices and edges.
* 聚类图Cluster graph是图的一种特例，其连接的组成部分视为团。
* '''<font color="#ff8000"> 聚类图Cluster graph</font>'''是图的一种特例，其连接的组成部分视为团。
* 框图Block graph是图的一种特例，其双连通的部分视为团。
* '''<font color="#ff8000"> 框图Block graph</font>'''是图的一种特例，其双连通的部分视为团。
* 弦图Chordal graph是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
* '''<font color="#ff8000"> 弦图Chordal graph</font>'''是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
* 余图Cograph是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
* '''<font color="#ff8000"> 余图Cograph</font>'''是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
* 区间图Interval graph是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
* '''<font color="#ff8000"> 区间图Interval graph</font>'''是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
* 线图Line graph是图的一种特例，其连边可以被不相交的边团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
* '''<font color="#ff8000"> 线图Line graph</font>'''是图的一种特例，其连边可以被不相交的边团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
* 完美图Perfect graph是图的一种特例，其导出子图的色数等于此导出子图的团数。
* '''<font color="#ff8000"> 完美图Perfect graph</font>'''是图的一种特例，其导出子图的色数等于此导出子图的团数。
* 分裂图Split graph是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
* '''<font color="#ff8000"> 分裂图Split graph</font>'''是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
* 三角形无关图Triangle-free graph是图的一种特例，除了顶点和连边之外，该图不含任何团。
* '''<font color="#ff8000"> 三角形无关图Triangle-free graph</font>'''是图的一种特例，除了顶点和连边之外，该图不含任何团。
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
此外，还有许多其他数学结构与图论的"团"有关。它们包括，
*The [[Intersection number (graph theory)|intersection number]] of a graph is the minimum number of cliques needed to cover all the graph's edges.
*The [[Intersection number (graph theory)|intersection number]] of a graph is the minimum number of cliques needed to cover all the graph's edges.
*The [[clique graph]] of a graph is the [[intersection graph]] of its maximal cliques.
*The [[clique graph]] of a graph is the [[intersection graph]] of its maximal cliques.
* 图G的团复形属于抽象复形，其中图G的每个团都为单纯形。
* 图G的'''<font color="#ff8000"> 团复形Clique complex</font>'''属于'''<font color="#ff8000"> 抽象复形Abstract simplicial complex</font>'''，其中图G的每个团都为单纯形。
* 单纯形图可记为无向图κ（G），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。
* '''<font color="#ff8000"> 单纯形图Simplex graph</font>'''可记为无向图κ（G），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。
* 团相加指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
* '''<font color="#ff8000"> 团相加Clique-sum</font>'''指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
* 团宽度是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。该图由最少数量的不同定点标签组成，并通过以下操作建立：
* '''<font color="#ff8000"> 团宽度Clique-width</font>'''是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。该图由最少数量的不同定点标签组成，并通过以下操作建立：
# 1.将两个已标记的图拆开，使其不相交；
# 1.将两个已标记的图拆开，使其不相交；
# 2.重新标记；
# 2.重新标记；
# 3.根据给定的标记，连接所有成对顶点。
# 3.根据给定的标记，连接所有成对顶点。
* 图的交叉数指的是能覆盖图所有连边所需的最小团数。
* 图的'''<font color="#ff8000"> 交叉数Intersection number</font>'''指的是能覆盖图所有连边所需的最小团数。
* 图G的团图指的是该图的极大团的交图。主要为了展示图G的团结构。
* 图G的'''<font color="#ff8000"> 团图Clique graph</font>'''指的是该图的极大团的交图。主要为了展示图G的团结构。