集團（圖理論）
- 23×1-Vertex集團（頂點），
- 42×2-Vertex集團（邊緣），
- 19×3-Vertex集團（輕和深藍色三角形）和
- 2×4-Vertex集團（深藍色區域）。
在圖理論的數學領域，一個集團（或者）是一個無向圖的頂點的子集，因此集團中的每個不同的頂點都相鄰。也就是說
儘管對完整子圖的研究至少可以追溯到Ramsey Theory的圖理論重新印象， Erdős＆Szekeres（1935） ，該詞集團一詞來自Luce＆Perry（1949） ，他們在社交網絡中使用完整的子圖來建模人們;也就是說，一群人彼此認識。集團在科學中，尤其是生物信息學中還有許多其他應用。
定義
在無向圖G =（ v ， e ）中的一個集團C是頂點的子集C v v ，因此每個兩個不同的頂點都相鄰。這等同於以下條件： C誘導的g的誘導子圖是一個完整的圖。在某些情況下，集團一詞也可以直接指代子圖。
最大集團是一個無法通過包含一個相鄰頂點來擴展的集團，即，一個不僅存在於較大集團的頂點集中的集團。一些作者以一種要求它們是最大的方式定義集團，並使用其他術語來用於完全不是最大的子圖。
圖G的最大集團是一個集團，因此沒有具有更多頂點的集團。此外，圖G的集團數ω （ g ）是G中最大集合中的頂點數。
G的交點是G的最小數量的集團，覆蓋G的所有邊緣。
圖G的集合封面數量是G的最小數量的cliques，其聯合涵蓋了圖的頂點V集。
圖形的最大集合橫向是頂點的子集，其屬性是該圖的每個最大集團在子集中至少包含一個頂點。
一個集團的相反是一個獨立的集合，從某種意義上說，每個集團都對應於補體圖中的獨立集。集團封面問題涉及找到盡可能少的集團，其中包括圖中的每個頂點。
一個相關的概念是一個雙分部分的雙分式概念。圖的兩分尺寸是覆蓋圖的所有邊緣所需的最小數量。
數學
有關集團的數學結果包括以下內容。
-
Turán的定理在密集圖中給出了一個集團的大小。如果圖具有足夠多的邊緣，則必須包含一個大集團。例如，每個圖表都帶有
頂點，超過
邊緣必須包含一個三個vertex集團。
- 拉姆齊（Ramsey）的定理指出，每個圖形或其補體圖都包含一個至少對數數量的頂點的集團。
- 根據Moon＆Moser（1965）的結果，具有3個頂點的圖最多可以具有3個N最大集團。遇到此界限的圖形是月球– Moser圖K 3,3，... ，這是Turán圖形作為Turán定理中極端情況的特殊情況。
- Hadwiger的猜想仍然未經證實，將圖（其Hadwiger編號）中最大的小數小調的大小與其色數有關。
- Erdős -Faber -Lovász的猜想將圖形著色與集團有關。
- Erdős– hajnal的猜想指出，由禁止圖表定義的圖形家族具有較大的集團或大量的cocliques 。
可以通過其集團來定義或表徵幾個重要的圖形類別：
- 群集圖是一個圖形，其連接的組件是集團。
- 塊圖是一個圖形，其雙連接組件是集團。
- 和弦圖是一個圖形，可以將頂點訂購為一個完美的消除順序，以使得每個頂點V的鄰居比順序中的v均為clique。
- cograph是所有最大集團與單個頂點中任何最大獨立設置相交的屬性的全部圖形。
- 間隔圖是一個圖形，其最大集團可以以這樣的方式排序，即對於每個頂點V ，包含V的集團在排序中都是連續的。
- 線圖是一個圖形，其邊緣可以被邊緣 - 界限集團覆蓋，以使每個頂點完全屬於封面中的兩個集團。
- 完美的圖是一個圖形，其中集團數等於每個引起的子圖中的色數。
- 拆分圖是一個圖，其中某些集團至少包含每個邊緣的一個端點。
- 無三角形的圖是一個圖形，除了其頂點和邊緣以外沒有其他集團。
此外，許多其他數學結構涉及圖中的集團。他們之中，
- 圖G的集團複合物是一個抽象的簡單複合物x （ g ），與G中的每個集團一起使用單純形
- 單純形圖是一個無向圖κ（ g ），在圖G中的每個集團和一個連接兩個與單個頂點不同的集團中的邊緣的頂點。它是中間圖的一個示例，與圖形集中的中間代數相關：三個集團A ， B和C的中間M （ a ， b ， c ）是該集團，其頂點至少屬於其頂點兩個集團A ， B和c 。
- 集團-SUM是一種通過共享集團合併兩個圖來組合兩個圖的方法。
- 集團寬度是圖表的複雜性，就從脫節工會，重新標記操作和將所有對頂點與給定標籤連接的所有對角度連接起來所需的不同頂點標籤的最小數量。具有集團寬度的圖形恰恰是集團的脫節工會。
- 圖的相交數是覆蓋所有圖形邊緣所需的最小群集數。
- 圖的集合圖是其最大插座的相交圖。
與完整子圖密切相關的概念是完整圖和完整圖形未成年人的細分。特別是， Kuratowski的定理和Wagner的定理分別通過禁止完整和完整的兩分細分和未成年人來表徵平面圖。
計算機科學
在計算機科學中，集團問題是在給定圖中找到最大集團或所有集團的計算問題。它是NP完整的，這是KARP的21個NP完整問題之一。它也是固定參數棘手的，難以近似。然而，已經開發了許多用於計算集團的算法，要么以指數時間（例如Bron -Kerbosch算法）運行，要么專門用於圖形族（例如平面圖），也可以在多項式時間內解決該問題。
申請
“集團”一詞在其圖理論用法中源自Luce＆Perry（1949）的工作，他們在社交網絡中使用完整的子圖（彼此認識的人群）使用完整的子圖紙。 Festinger（1949）在使用較少技術術語的文章中使用了相同的定義。兩種作品都涉及使用矩陣在社交網絡中發現集團。為了從理論上以圖形方式建模社會集團的努力，請參見Eg Alba（1973） ， Peay（1974）和Doreian＆Woodard（1994） 。
使用集團對生物信息學的許多不同問題進行了建模。例如， Ben-Dor，Shamir＆Yakhini（1999）模擬了將基因表達數據聚類的問題作為找到將圖形描述數據轉換為形成圖形的圖形所需的最小變化數量之一，該圖形形成了群集的不相交。 Tanay，Sharan＆Shamir（2002）討論了表達數據的類似雙簇問題，其中簇必須為集團。 Sugihara（1984）使用集團在食物網中對生態壁cor進行建模。 Day＆Sankoff（1986）將推斷進化樹的問題描述為在圖中找到最大集量之一，該圖作為該物種的頂點特徵，如果存在完美的系統發育結合了這兩個字符，則兩個頂點具有優勢。 Samudrala＆Moult（1998）模擬蛋白質結構預測是在圖表中找到集團的問題，其頂點代表蛋白質亞基的位置。 Spirin＆Mirny（2003）通過搜索蛋白質 - 蛋白質相互作用網絡中的簇，發現了蛋白質簇，這些蛋白質群體相互緊密相互作用，並且與簇外的蛋白質幾乎沒有相互作用。功率圖分析是一種通過在這些網絡中找到集團和相關結構來簡化複雜生物網絡的方法。
在電氣工程中， Prihar（1956）使用集團來分析通信網絡， Paull＆Unger（1959）使用它們來設計有效的電路，以計算部分指定的布爾函數。集團也已用於自動測試模式生成：可能故障不兼容圖中的一個大集團為測試集的大小提供了下限。 Cong＆Smith（1993）描述了集團在將電子電路的分層分區中的分區應用到較小的亞基中的應用。
在化學中，羅德斯等人。 （2003）使用集團在化學數據庫中描述與目標結構相似的化學物質。 Kuhl，Crippen＆Friesen（1983）使用集團對兩種化學物質相互結合的位置進行建模。