圖中的團

---

最近，基於圖的表示在模擬現實世界資料方面獲得了極大的普及。團是圖論中的一個關鍵問題，用於解決許多數學問題和建立圖形。團在計算機科學領域得到了廣泛的研究，其中團問題評估圖中是否存在一定大小的團，這是一個 NP 完全問題。然而，儘管存在所有複雜性，但人們一直在研究幾種查詢團的技術。

什麼是團？

在所有無向圖 G = (N, E) 中，團是“節點的子集”，使得所有成對的不同節點都是相鄰的。指定圖的完全子圖是無向圖中的團。完全子圖具有所有與圖中所有其他頂點連線的頂點。獨立集是在補圖中團的對立面，因為每個團都類似於一個獨立集。在考慮圖的所有頂點的情況下，找到圖的最小團被稱為團覆蓋問題。

最大團是指不能透過新增另一個相鄰節點進一步擴大的團。

在圖中，最大團是指沒有其他團具有更多頂點的團。此外，具有最大團的圖中節點的總數稱為團數。

因此，最大團也是最大團（但反之不一定成立）。

什麼是 K-團？

大小為 k 的團稱為“k-團”（但是，這個詞有時也用於指代距離不超過 k 的最大頂點組）。0-團表示空集（沒有頂點的集合），“1-團”表示節點，2-團表示邊，“3-迴圈”由 3-團表示。

關於團有哪些定理？

根據 Ramsey 定理，任何圖或其補圖中都存在至少具有對數數量節點的團。

“Turán 定理”限制了稠密圖中團的大小。如果圖包含足夠的邊，則存在一個巨大的團。例如，任何具有 m 個節點且大於 [m/2][m/2] 條邊的圖中都必須存在一個三頂點團。

Moon 和 Moser 證明，在具有 3n 個節點的圖中，最多隻能有 3n3 個最大團。Moon-Moser 圖滿足此限制。

基於團的圖分類

可以使用它們的團來描述或分類各種主要型別的圖 -

圖	特徵
“聚類圖”	團是其連通分量的圖
“塊圖”	團是其雙連通分量的圖。
“分裂圖”	圖中每條邊的至少一個頂點都屬於團。
“無三角形圖”	除了其邊和頂點之外，沒有其他團的圖
“線圖”	圖的邊可以用“邊不相交的團”覆蓋，這意味著覆蓋中的每個頂點都恰好是兩個團的成員。

團問題

團問題是一個計算任務，您必須在其中找到圖中的團。它包括許多基於必須識別團的位置以及必須獲得關於它們的哪種型別的資訊的公式。

識別“最大團”、為加權圖找到“最大權重團”、識別最大團以及確定任何圖是否包含大於某個大小的團構成了構建團問題的核心方法。

解決大多數團問題都是具有挑戰性的。團選擇問題是“Karp 的 21 個 NP 完全問題”之一。找到最大的團在具有集合引數且難以量化的情況下很複雜。此外，由於存在許多具有指數級最大團的圖，因此識別每個最大團可能需要指數級時間。

識別單個最大團

一個簡單的貪婪演算法可以確定最大的團。透過迭代圖的所有頂點，從任何團（只有一個節點或可能是整個集合）開始，我們一次新增一個節點來增長當前團。對於此迭代檢查的每個頂點，如果特定頂點與每個其他頂點都相鄰，則將頂點新增到團中，否則忽略它。該演算法在時間上是線性的。由於最大團很容易發現，並且它們可能具有最小的大小，因此人們更多地關注尋找大團這個更困難的計算過程，而不是尋找單個最大團的難度。

使用“蠻力”演算法，可以確定圖是否包含“k-頂點團”並識別其中包含的每個這樣的團。此方法檢查每個具有 k 個節點的子圖以檢視它是否是團的一部分。在大的 O 表示法中，它需要 O(nkk2) 時間。這是因為存在 O(nk) 個子圖需要檢查，所有這些子圖都有 O(k2) 條邊需要驗證。因此，當 k 是一個給定的常數時，問題在時間上是多項式的。當 k 沒有固定值並且作為問題輸入的一部分發生變化時，時間變得呈指數級。

固定大小的團

識別所有最大團

“Bron-Kerbosch”方法用於在每個團的多項式時間內以及最壞情況下的最優時間內識別每個最大團。根據 Moon 和 Moser，每個 n-頂點網路最多可以有 3n3 個最大團，並且“Bron-Kerbosch”方法（透過一種關鍵方法減少每個階段執行的遞迴呼叫次數）的最壞情況執行時間為 O(3n3)，這與該限制相匹配。

團的應用有哪些？

假設一個線上社群，其中圖的節點表示人員，邊表示互惠的聯絡。術語“團”是指一群彼此都認識的人。可以使用用於檢測團的演算法來找到這些朋友網路。

Kuhl、Crippen 和 Friesen 在計算化學中使用團來表示兩個分子鍵合的點。

為部分指定的布林函式建立高效電路。

結論

團在圖分析中至關重要，並且通常用於解決數學問題和建立圖形。儘管“團問題是 NP 完全的”，但人們正在研究各種用於檢測團的演算法。K-團是指大小為 k 的團，並且存在關於團的各種定理。它們在計算機科學、生物資訊學和圖論中有多種應用。