961
个编辑
更改
跳到导航
跳到搜索
第9行：
第9行： − − 第17行：
第15行： − 在图论的数学领域中，团(或)是无向图的顶点的子集，使得团中每两个不同的顶点相邻，即它的导出子图是完全的。团是图论的基本概念之一，在许多其他数学问题和图的构造中也有应用。团问题在计算机科学中也有研究: 在一个图中是否存在一个给定大小的团(团问题)是 np 完全问题，但是尽管这个结果很困难，许多寻找团的算法已经被研究过。+ 第25行：
第23行： − 虽然完全子图的研究至少可以追溯到 Ramsey 理论的图论重构，但是术语团来源于，他们在社会网络中使用完全子图来模拟人们的团体，即相互认识的人们的团体。小集团在科学，特别是在生物信息学中有许多其他的应用。+ 第35行：
第33行： − 无向图(v，e)}中的团 c 是顶点的子集，使得每两个不同的顶点相邻。这等价于由 c 导出的 g 的导出子图是完全图的条件。在某些情况下，团这个术语也可以直接指子图。+ 第43行：
第41行： − 最大团是一个不能通过包含多个相邻顶点而扩展的团，即不仅仅存在于一个较大团的顶点集中的团。有些作者定义团的方式要求它们是极大的，并使用其他术语来定义不是极大的完全子图。+ 第51行：
第49行： − 一个图 g 的最大团是一个团，这样就不存在多顶点的团。此外，图 g 的团数(g)是图 g 的最大团中的顶点数。+ 第59行：
第57行： − G 的交集数是覆盖 g 的所有边的团的最小个数。+ 第75行：
第73行： − 图的最大团横截是指图的每个最大团在子集中至少包含一个顶点的顶点子集。+ 第83行：
第81行： − 团体的对立面是一个独立的集合，在某种意义上说，每个团体对应于补图中的一个独立的集合。分团覆盖问题关注于寻找尽可能少的包含图中每个顶点的团。+ 第91行：
第89行： − 一个相关的概念是双列，一个完全二部子图。图的二部维数是覆盖图的所有边所需的最小双曲数。+ − + + + − Mathematical results concerning cliques include the following. − 关于小团体的数学结果包括以下内容。 − − − + − + + + + + + + − Several important classes of graphs may be defined or characterized by their cliques: − 图的几个重要类别可以定义或拥有属性它们的团: − − − − − − − + − + + + + + + + + + + + − Additionally, many other mathematical constructions involve cliques in graphs. Among them, − 此外，许多其他的数学构造也涉及图中的团。其中, − − − − − − + − + + + + + + + + + 第165行：
第170行： − 与完备子图密切相关的概念是完备图的子图和完备图子图的子图。特别地，库拉托斯基定理和瓦格纳定理分别用禁止完全和完全二部分细分图以及子图刻画了平面图。+
无编辑摘要
11个浅蓝色三角形（三顶点团）为极大团。深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
11个浅蓝色三角形（三顶点团）为极大团。深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
]]
]]
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
在图论的数学领域中，团是无向图中顶点的子集，使得一个团中每两个不同的顶点必定相邻。也就是说，其导出子图是完全图。团是图论的基本概念之一，可用于图形的构建和解决许多其他数学问题。而且，在计算机科学领域中也经常会涉及到团的研究：比如在一个给定规模的图中寻找团的存在就是一个NP-完全问题。尽管我们已经明确知道这个问题很难得以解决，但仍然有许多学者在研究用于寻找团的算法。
Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics.
Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics.
对完全子图的研究至少可以追溯到拉姆齐定理中的图论重组，由Erdős＆Szekeres（1935）在论文《A combinatorial problem in geometry》提出的。但实际上“团”一词是来自Luce＆Perry（1949）的文章《A method of matrix analysis of group structure》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。
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.
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的导出子集，进而将此过程视为由C引导出的完全子集的成立条件。在某些情况下，“团”这一术语也可以直接被引用为子集。
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal.
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal.
极大团Maximal clique也是一个团，但是该团不能通过合并更多的相邻节点而进行扩张，换句话说，该团不可能被更大的团所包含。有些学者将“极大团”定义为“团”，而建议用其他术语来重新定义“非极大团”。
A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, the clique number ω(G) of a graph G is the number of vertices in a maximum clique in G.
A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, the clique number ω(G) of a graph G is the number of vertices in a maximum clique in G.
图G中同样存在一个最大团，使得其不存在更多顶点。另外，图G的团数ω（G）是该图最大团的顶点数。
The intersection number of G is the smallest number of cliques that together cover all edges of G.
The intersection number of G is the smallest number of cliques that together cover all edges of G.
图G的交叉数是该图中能覆盖所有连边的最少团数。
A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.
A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.
一个图的最大团横贯集是其顶点的子集，其属性为该图的每个最大团中至少有一个顶点在最大团横贯集中。
The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. The clique cover problem concerns finding as few cliques as possible that include every vertex in the graph.
The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. The clique cover problem concerns finding as few cliques as possible that include every vertex in the graph.
作为团的对立面，独立集的存在是指图中两两互相不相邻的顶点集合。因此，每一个团都对应于补图中的独立集。集团覆盖问题涉及到寻找尽可能少的团，其中就包括图中的每个顶点。
A related concept is a biclique, a complete bipartite subgraph. The bipartite dimension of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
A related concept is a biclique, a complete bipartite subgraph. The bipartite dimension of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
二元团是团的相关概念，指的是一个完全二分图。该图的二分维度指的是覆盖该图所有连边的最少二元团数。
==Mathematics==
== Mathematics 数学运算==
Mathematical results concerning cliques include the following.
Mathematical results concerning cliques include the following.
Mathematical results concerning cliques include the following.
有关“团”的数学结论包括以下内容。
*[[Turán's theorem]] gives a [[lower bound]] on the size of a clique in [[dense graph]]s.{{sfnp|Turán|1941}} If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with <math>n</math> vertices and more than <math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math> edges must contain a three-vertex clique.
*[[Turán's theorem]] gives a [[lower bound]] on the size of a clique in [[dense graph]]s.{{sfnp|Turán|1941}} If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with <math>n</math> vertices and more than <math>\scriptstyle\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil</math> edges must contain a three-vertex clique.
*[[Ramsey's theorem]] states that every graph or its [[complement graph]] contains a clique with at least a logarithmic number of vertices.{{sfnp|Graham|Rothschild|Spencer|1990}}
*[[Ramsey's theorem]] states that every graph or its [[complement graph]] contains a clique with at least a logarithmic number of vertices.{{sfnp|Graham|Rothschild|Spencer|1990}}
*According to a result of {{harvtxt|Moon|Moser|1965}}, a graph with 3''n'' vertices can have at most 3<sup>''n''</sup> maximal cliques. The graphs meeting this bound are the Moon–Moser graphs ''K''<sub>3,3,...</sub>, a special case of the [[Turán graph]]s arising as the extremal cases in Turán's theorem.
*According to a result of {{harvtxt|Moon|Moser|1965}}, a graph with 3''n'' vertices can have at most 3<sup>''n''</sup> maximal cliques. The graphs meeting this bound are the Moon–Moser graphs ''K''<sub>3,3,...</sub>, a special case of the [[Turán graph]]s arising as the extremal cases in Turán's theorem.
*[[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]], still unproven, relates the size of the largest clique [[graph minor|minor]] in a graph (its [[Hadwiger number]]) to its [[chromatic number]].
*[[Hadwiger conjecture (graph theory)|Hadwiger's conjecture]], still unproven, relates the size of the largest clique [[graph minor|minor]] in a graph (its [[Hadwiger number]]) to its [[chromatic number]].
*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个顶点且超过个边的图形都必然含一个三顶点团。
* 拉姆齐定理指出，每个图或其补图都包含至少一个具有对数个顶点的团。
* 根据Moon＆Moser（1965）的研究结果，一个具有3n个顶点的图最多可以有3n个极大团。满足此极限要求的图被称为Moon＆Moser图K3,3，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
* 关于Hadwiger的猜想，目前尚未得到证实，其认为图中最大的团子式的大小（即Hadwiger数）与其色数相关。
* Erdős–Faber–Lovász猜想是另一个未经证实的陈述，同样认为图的着色与团相关。
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 [[cluster graph]] is a graph whose [[connected component (graph theory)|connected components]] are cliques.
*A [[cluster graph]] is a graph whose [[connected component (graph theory)|connected components]] are cliques.
*A [[block graph]] is a graph whose [[biconnected component]]s are cliques.
*A [[block graph]] is a graph whose [[biconnected component]]s are cliques.
*A [[chordal graph]] is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the [[neighborhood (graph theory)|neighbors]] of each vertex ''v'' that come later than ''v'' in the ordering form a clique.
*A [[chordal graph]] is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the [[neighborhood (graph theory)|neighbors]] of each vertex ''v'' that come later than ''v'' in the ordering form a clique.
*A [[cograph]] is a graph all of whose induced subgraphs have the property that any maximal clique intersects any [[maximal independent set]] in a single vertex.
*A [[cograph]] is a graph all of whose induced subgraphs have the property that any maximal clique intersects any [[maximal independent set]] in a single vertex.
*An [[interval graph]] is a graph whose maximal cliques can be ordered in such a way that, for each vertex ''v'', the cliques containing ''v'' are consecutive in the ordering.
*An [[interval graph]] is a graph whose maximal cliques can be ordered in such a way that, for each vertex ''v'', the cliques containing ''v'' are consecutive in the ordering.
*A [[line graph]] is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
*A [[line graph]] is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
*A [[perfect graph]] is a graph in which the clique number equals the [[chromatic number]] in every [[induced subgraph]].
*A [[perfect graph]] is a graph in which the clique number equals the [[chromatic number]] in every [[induced subgraph]].
*A [[split graph]] is a graph in which some clique contains at least one endpoint of every edge.
*A [[split graph]] is a graph in which some clique contains at least one endpoint of every edge.
*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是图的一种特例，其连接的组成部分视为团。
* 框图Block graph是图的一种特例，其双连通的部分视为团。
* 弦图Chordal graph是图的一种特例，其顶点可以按照最佳删除顺序进行排序；也就是说每个顶点的相邻点（即与其构成一个团的另一个顶点）为该顶点的后续点。
* 余图Cograph是图的一种特例，其所有的导出子图均具有以下特性：任何极大团与任何极大独立集都相交于一个独立点。
* 区间图Interval graph是图的一种特例，其极大团按照一定顺序排列，对于每个顶点v,所有包含其顶点v的团均连续排列。
* 线图Line graph是图的一种特例，其连边可以被不相交的边团覆盖，从而使得每个顶点恰好属于该覆盖区域中的两个团。
* 完美图Perfect graph是图的一种特例，其导出子图的色数等于此导出子图的团数。
* 分裂图Split graph是图的一种特例，其中存在某个团包含至少一个顶点，该顶点为每条边的端点。
* 三角形无关图Triangle-free graph是图的一种特例，除了顶点和连边之外，该图不含任何团。
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 [[clique complex]] of a graph ''G'' is an [[abstract simplicial complex]] ''X''(''G'') with a simplex for every clique in ''G''
*The [[clique complex]] of a graph ''G'' is an [[abstract simplicial complex]] ''X''(''G'') with a simplex for every clique in ''G''
*A [[simplex graph]] is an undirected graph κ(''G'') with a vertex for every clique in a graph ''G'' and an edge connecting two cliques that differ by a single vertex. It is an example of [[median graph]], and is associated with a [[median algebra]] on the cliques of a graph: the median ''m''(''A'',''B'',''C'') of three cliques ''A'', ''B'', and ''C'' is the clique whose vertices belong to at least two of the cliques ''A'', ''B'', and ''C''.<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref>
*A [[simplex graph]] is an undirected graph κ(''G'') with a vertex for every clique in a graph ''G'' and an edge connecting two cliques that differ by a single vertex. It is an example of [[median graph]], and is associated with a [[median algebra]] on the cliques of a graph: the median ''m''(''A'',''B'',''C'') of three cliques ''A'', ''B'', and ''C'' is the clique whose vertices belong to at least two of the cliques ''A'', ''B'', and ''C''.<ref>{{harvtxt|Barthélemy|Leclerc|Monjardet|1986}}, page 200.</ref>
*The [[clique-sum]] is a method for combining two graphs by merging them along a shared clique.
*The [[clique-sum]] is a method for combining two graphs by merging them along a shared clique.
*[[Clique-width]] is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques.
*[[Clique-width]] is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques.
*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），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。
* 团相加指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
* 团宽度是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。该图由最少数量的不同定点标签组成，并通过以下操作建立：
# 1.将两个已标记的图拆开，使其不相交；
# 2.重新标记；
# 3.根据给定的标记，连接所有成对顶点。
* 图的交叉数指的是能覆盖图所有连边所需的最小团数。
* 图G的团图指的是该图的极大团的交图。主要为了展示图G的团结构。
* 从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。
Closely related concepts to complete subgraphs are [[subdivision (graph theory)|subdivision]]s of complete graphs and complete [[graph minor]]s. In particular, [[Kuratowski's theorem]] and [[Wagner's theorem]] characterize [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subdivisions and minors, respectively.
Closely related concepts to complete subgraphs are [[subdivision (graph theory)|subdivision]]s of complete graphs and complete [[graph minor]]s. In particular, [[Kuratowski's theorem]] and [[Wagner's theorem]] characterize [[planar graph]]s by forbidden complete and [[complete bipartite graph|complete bipartite]] subdivisions and minors, respectively.
Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graphs by forbidden complete and complete bipartite subdivisions and minors, respectively.
Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graphs by forbidden complete and complete bipartite subdivisions and minors, respectively.
从概念上来说，完全子图与完全图细分，以及完全图子式密切相关。尤其是Kuratowski定理和Wagner定理，它们就是通过禁用完全图、完全二分图细分和完全二分图子式来描述平面图特征的。