團 (圖論)

圖論領域的一個無向圖中,滿足兩兩之間有連接的頂點集合,被稱為該無向圖的團。團是圖論中的基本概念之一,用在很多數學問題以及圖的構造上。計算機科學中也有對它的研究,儘管在一個圖中尋找給定大小的團達到了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的補圖中的獨立集是一一對應的。

相關性質

相關定理

  • 圖蘭定理給出了稠密圖中團的大小的下界。[2]如果一張圖有足夠多條邊,那麼它肯定包含一個大團。例如,對於任意 階圖,如果它的邊數大於 ,那麼它必然包含一個 階團。
  • 拉姆齊定理指出,任意圖或者它的補圖包含這樣的團,它具有至少為對數大小的點數。[3]
  • Moon & Moser 指出,階數為 的圖至多有 個極大團。極大值在 Moon-Moser 圖 取得,這是圖蘭圖英語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)更早提出完全子圖一詞(一個有限圖是平面圖,若且唯若它不包含完全子圖完全二分子圖),但作者在最初的措辭著意於拓撲術語,而非圖論術語.
  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 
  4. ^ Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 1965, 3: 23–28, MR 0182577, doi:10.1007/BF02760024 

參考文獻

外部連結