團 (圖論)

在圖論領域的一個無向圖中，滿足兩兩之間有邊連接的頂點的集合，被稱為該無向圖的團。團是圖論中的基本概念之一，用在很多數學問題以及圖的構造上。計算機科學中也有對它的研究，儘管在一個圖中尋找給定大小的團達到了NP完全的難度，人們還是研究過很多尋找團的算法。

雖然對完全子圖的研究可以追溯到Erdős & Szekeres (1935)中拉姆齊理論對圖理論的重組^[1]，「團」這一術語本身其實源自 Luce & Perry (1949)，那篇文章中社會網絡的完全子圖被用來模擬一「團」人，也就是一組兩兩相互認識的人。團在科學領域特別是在生物信息學中有許多其他應用。

定義

頂點集C被稱為無向圖 G=(V,E) 的團，如果C是頂點集V的子集(C⊆V)，而且任意兩個C中的頂點都有邊連接。另一種等價的說法是，由C誘導的子圖是完全圖 （有時也用「團」來指這樣的子圖）。

極大團是指增加任一頂點都不再符合團定義的團，也就是說，極大團不能被任何一個更大的團所包含。

最大團是一個圖中頂點數最多的團。圖G的團數（clique number）ω(G) 是指G中最大團的頂點數。圖G的邊團覆蓋數（edge clique cover number）是指覆蓋G中所有的邊所需要的最少的團的數目。圖G的二分維數（英語：Bipartite dimension）是指覆蓋G中所有邊所需要的最少的二分團的數目，其中二分團（biclique）就是完全二分子圖 。而分團覆蓋問題 （Clique cover problem）所關心的是用最少的團去覆蓋G中所有的頂點。

獨立集是剛好和團相反的概念，因為圖G中的團和圖G的補圖中的獨立集是一一對應的。

相關性質

• Cluster graph（英語：Cluster_graph）的連通分量為團。
• Block graph（英語：Block_graph）的2-連通分量（英語：Biconnected_component）為團。
• 弦圖的點具有完美消去序（perfect elimination ordering），這種排序具有如下性質：對於所有的點${\displaystyle v}$，${\displaystyle N(v)}$中排序在${\displaystyle v}$後的點和${\displaystyle v}$共同構成一個團。
• Cograph（英語：Cograph）的所有導出子圖具有如下性質：任意極大團與任意極大獨立集（英語：Maximal_independent_set）有且僅有一個共同點。
• Interval graph（英語：Interval_graph）的極大團可以按照如下方式排序：對於任意點${\displaystyle v}$包含${\displaystyle v}$的團在排序中是連續的。
• 線圖的邊能被一些沒有公共邊的團所覆蓋，並且每個點恰好屬於兩個團。
• 完美圖（英語：Perfect_graph）的所有導出子圖的團數等於色數。
• Split graph（英語：Split_graph）包含具有如下性質的團：對於圖中每條邊，至少包含一個頂點。
• Triangle-free graph（英語：Triangle-free_graph）的團數至多為2。

相關定理

• 圖蘭定理給出了稠密圖中團的大小的下界。^[2]如果一張圖有足夠多條邊，那麼它肯定包含一個大團。例如，對於任意${\displaystyle n}$階圖，如果它的邊數大於${\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil }$，那麼它必然包含一個${\displaystyle 3}$階團。
• 拉姆齊定理指出，任意圖或者它的補圖包含這樣的團，它具有至少為對數大小的點數。^[3]
• Moon & Moser 指出，階數為${\displaystyle 3n}$的圖至多有${\displaystyle 3^{n}}$個極大團。極大值在 Moon-Moser 圖${\displaystyle K_{3,3,\dots }}$取得，這是圖蘭圖（英語：Turán_graph）的在圖蘭定理下的一種極端情況。^[4]
• Hadwiger猜想（英語：Hadwiger_conjecture_(graph_theory)）給出了最大團大小與色數之間的關係。
• Erdős–Faber–Lovász猜想（英語：Erdős–Faber–Lovász_conjecture）給出了圖着色與團之間的關係。

分團問題

主條目：分團問題

在計算複雜性理論中，分團問題（clique problem）在給定圖中尋找最大團的問題。它是圖論中的一個NP完全問題。人們在分團問題上提出了許多算法，指數時間複雜度算法包括Bron–Kerbosch算法（英語：Bron–Kerbosch_algorithm），而針對特定一類圖有多項式時間複雜度算法，例如平面圖和完美圖（英語：Perfect_graph）。

註釋

1. 其實Kuratowski (1930) harvtxt error: no target: CITEREFKuratowski1930 (help)更早提出完全子圖一詞（一個有限圖是平面圖，若且唯若它不包含完全子圖或完全二分子圖），但作者在最初的措辭着意於拓撲術語，而非圖論術語.
2. Turán, Paul, On an extremal problem in graph theory, Matematikai és Fizikai Lapok, 1941, 48: 436–452 （匈牙利語）
3. Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory, New York: John Wiley and Sons, 1990, ISBN 978-0-471-50046-9 含有內容需登入查看的頁面 (link)
4. Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 1965, 3: 23–28, MR 0182577, doi:10.1007/BF02760024

參考文獻

• Erdős, Paul; Szekeres, George, A combinatorial problem in geometry (PDF), Compositio Math., 1935, 2: 463–470 [2013-08-22], （原始內容存檔 (PDF)於2020-05-22）.

• [R. Duncan]; Perry, Albert D., A method of matrix analysis of group structure, Psychometrika, 1949, 14 (2): 95–116, PMID 18152948, doi:10.1007/BF02289146 請檢查|author-link1=值 (幫助).

外部連結

• 埃里克·韋斯坦因. Clique. MathWorld.
• 埃里克·韋斯坦因. Clique Number. MathWorld.