团（图论） - 版本历史

2021年12月30日 (四) 12:41 薄荷

2021-12-30T12:41:36Z

2021年12月30日 (四) 12:39 薄荷

2021-12-30T12:39:40Z

2021年12月30日 (四) 12:38 薄荷

2021-12-30T12:38:40Z

2021年12月30日 (四) 12:37 薄荷

2021-12-30T12:37:55Z

2021年12月30日 (四) 12:36 薄荷

2021-12-30T12:36:17Z

2021年12月30日 (四) 12:35 薄荷

2021-12-30T12:35:08Z

2021年12月30日 (四) 12:34 薄荷

2021-12-30T12:34:46Z

2021年12月30日 (四) 12:18 薄荷

2021-12-30T12:18:00Z

显示更改

2021年2月25日 (四) 10:31 Flipped

2021-02-25T10:31:03Z

显示更改

Jie：/* Mathematics 数学运算 */

2020-08-26T01:44:18Z

Mathematics 数学运算

@@ 第144行： / 第144行： @@
 *{{citation |title=Defining and locating cores and boundaries of social networks |first1=Patrick |last1=Doreian |first2=Katherine L. |last2=Woodard |journal=Social Networks |volume=16 |issue=4 |year=1994 |pages=267–293 |doi=10.1016/0378-8733(94)90013-2}}.
-*{{citation |first1=Paul |last1=Erdős |author1-link=Paul Erdős |first2=George |last2=Szekeres |author2-link=George Szekeres |title=A combinatorial problem in geometry |journal=Compositio Mathematica |volume=2 |year=1935 |pages=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf}}.
+*{{citation |first1=Paul |last1=Erdős |first2=George |last2=Szekeres |title=A combinatorial problem in geometry |journal=Compositio Mathematica |volume=2 |year=1935 |pages=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf}}.
 *{{citation |doi=10.1177/001872674900200205 |first=Leon |last=Festinger |title=The analysis of sociograms using matrix algebra |journal=Human Relations |year=1949 |volume=2 |issue=2 |pages=153–158 }}.
@@ 第151行： / 第151行： @@
   | last1 = Graham
   | first1 = R.
   | last2 = Rothschild
   | first2 = B.
   | last3 = Spencer
   | first3 = J. H.
   | location = New York
   | publisher = John Wiley and Sons
@@ 第168行： / 第166行： @@
 *{{citation |last1=Hamzaoglu |first1=I. |last2=Patel |first2=J. H. |contribution=Test set compaction algorithms for combinational circuits |title=Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design |year=1998 |pages=283–289 |doi=10.1145/288548.288615|isbn=978-1581130089 }}.
-*{{citation | last=Karp |first=Richard M. |authorlink = Richard M. Karp | url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |contribution= Reducibility among combinatorial problems | title = Complexity of Computer Computations | editor1-first = R. E. |editor1-last=Miller |editor2-first=J. W. |editor2-last=Thatcher | publisher = New York: Plenum | pages = 85&ndash;103 | year = 1972}}.
+*{{citation | last=Karp |first=Richard M. | url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |contribution= Reducibility among combinatorial problems | title = Complexity of Computer Computations | editor1-first = R. E. |editor1-last=Miller |editor2-first=J. W. |editor2-last=Thatcher | publisher = New York: Plenum | pages = 85&ndash;103 | year = 1972}}.
 *{{citation |first1=F. S. |last1=Kuhl |first2=G. M. |last2=Crippen |first3=D. K. |last3=Friesen |year=1983 |title=A combinatorial algorithm for calculating ligand binding |journal=Journal of Computational Chemistry |doi=10.1002/jcc.540050105 |volume=5 |issue=1 |pages=24–34}}.
-*{{citation |first=Kazimierz |last=Kuratowski |authorlink=Kazimierz Kuratowski |language=French |title=Sur le problème des courbes gauches en Topologie |journal=Fundamenta Mathematicae |volume=15 |year=1930 |pages=271–283 |url=http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf|doi=10.4064/fm-15-1-271-283 }}.
+*{{citation |first=Kazimierz |last=Kuratowski |language=French |title=Sur le problème des courbes gauches en Topologie |journal=Fundamenta Mathematicae |volume=15 |year=1930 |pages=271–283 |url=http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf|doi=10.4064/fm-15-1-271-283 }}.
 *{{citation
-  | last1 = Luce | first1 = R. Duncan | author1-link = R. Duncan Luce
+  | last1 = Luce | first1 = R. Duncan
   | last2 = Perry | first2 = Albert D.
   | title = A method of matrix analysis of group structure
   | journal = Psychometrika | volume = 14 | issue = 2 | year = 1949
   | pages = 95–116 | doi = 10.1007/BF02289146
-  | pmid = 18152948| hdl = 10.1007/BF02289146 | s2cid = 16186758 | hdl-access = free }}.
+  | pmid = 18152948| hdl = 10.1007/BF02289146 | hdl-access = free }}.
 *{{citation
-  | last1 = Moon | first1 = J. W. | author2-link = Leo Moser | last2 = Moser | first2 = L.
+  | last1 = Moon | first1 = J. W. | last2 = Moser | first2 = L.
   | title = On cliques in graphs
   | journal = [[Israel Journal of Mathematics]]
@@ 第209行： / 第207行： @@
 *{{citation
   | last = Turán
-  | first = Paul | author-link = Pál Turán
+  | first = Paul
   | year = 1941
   | title = On an extremal problem in graph theory

←上一版本		2021年12月30日 (四) 12:39的版本
第16行：		第16行：


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

@@ 第6行： / 第6行： @@
 [[文件:VR complex.svg|缩略图|
 *23个单顶点团（顶点）<br>
-*42个双顶点团（边）
+*42个双顶点团（边）<br>
-*19个三顶点团（浅色和深色的三角形）
+*19个三顶点团（浅色和深色的三角形）<br>
-*2个四顶点团（深色区域）
+*2个四顶点团（深色区域）<br>
-*11个浅蓝色三角形（三顶点团）为极大团
+*11个浅蓝色三角形（三顶点团）为极大团<br>
 *2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
 ]]

@@ 第5行： / 第5行： @@
 [[文件:VR complex.svg|缩略图|
-*23个单顶点团（顶点）
+*23个单顶点团（顶点）<br>
 *42个双顶点团（边）
 *19个三顶点团（浅色和深色的三角形）

@@ 第5行： / 第5行： @@
 [[文件:VR complex.svg|缩略图|
-•	23个单顶点团（顶点）
+*23个单顶点团（顶点）
-•	42个双顶点团（边）
+*42个双顶点团（边）
-•	19个三顶点团（浅色和深色的三角形）
+*19个三顶点团（浅色和深色的三角形）
-•	2个四顶点团（深色区域）
+*2个四顶点团（深色区域）
-个浅蓝色三角形（三顶点团）为极大团。2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
+*11个浅蓝色三角形（三顶点团）为极大团
 ]]

←上一版本		2021年12月30日 (四) 12:35的版本
第15行：		第15行：


−	对完全子图的研究至少可以追溯到'''拉姆齐定理 Ramsey's theorem'''中的图论重组，由Erdős＆Szekeres（1935）在论文A combinatorial problem in geometry《几何组合问题》提出的。<ref>The earlier work by {{harvtxt\|Kuratowski\|1930}} characterizing [[planar graph]]s by forbidden complete and [[complete bipartite graph\|complete bipartite]] subgraphs was originally phrased in topological rather than graph-theoretic terms.</ref>但实际上“团”一词是来自Luce＆Perry（1949）的论文《群结构矩阵分析的一种方法 A method of matrix analysis of group structure》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。	+	对完全子图的研究至少可以追溯到'''拉姆齐定理 Ramsey's theorem'''中的图论重组，由Erdős＆Szekeres（1935）在论文A combinatorial problem in geometry《几何组合问题》提出的。但实际上“团”一词是来自Luce＆Perry（1949）的论文《群结构矩阵分析的一种方法 A method of matrix analysis of group structure》，后者在社交网络中使用完全子图来对人群进行建模；该模型定义在这群人中，所有人是互相认识的。其实团这一概念在诸多科学领域中均有所应用，尤其是在生物信息学。

@@ 第5行： / 第5行： @@
 [[文件: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个四顶点团（深色区域）
 个浅蓝色三角形（三顶点团）为极大团。2个深蓝色的四顶点团既是最大团也是极大团，该图的团数是4。
 ]]
@@ 第19行： / 第18行： @@
-== Definitions 定义 ==
+== 定义 ==
 在一个无向图''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，...，该图相当于托兰图的特例，是托兰定理中的极端情况。
@@ 第224行： / 第218行： @@
 {{refend}}
-此词条由Jie初步翻译，由Flipped审校。
+[[Category:图论对象]]

@@ 第154行： / 第154行： @@
 *The [[clique graph]] of a graph is the [[intersection graph]] of its maximal cliques.
 * 图G的'''<font color="#ff8000"> 团复形Clique complex</font>'''属于'''<font color="#ff8000"> 抽象复形Abstract simplicial complex</font>'''，其中图G的每个团都为单纯形。
-* '''<font color="#ff8000"> 单纯形图Simplex graph</font>'''可记为无向图κ（G），它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。
+* '''<font color="#ff8000"> 单纯形图Simplex graph</font>'''可记为无向图''κ（G）''，它具有图G中每个团的一个顶点，以及一个连边，并且该连边通过一个顶点将两个不同的团相连。
 * '''<font color="#ff8000"> 团相加Clique-sum</font>'''指的是将两个图合并，沿着他们共有团的顶点和连边融合形成。
 * '''<font color="#ff8000"> 团宽度Clique-width</font>'''是图复杂性的一个概念，是用来说明图结构复杂性的一个参数。该图由最少数量的不同定点标签组成，并通过以下操作建立：