圖論領域的一個無向圖中,滿足兩兩之間有連接的頂點集合,被稱為該無向圖的團。團是圖論中的基本概念之一,用在很多數學問題以及圖的構造上。計算機科學中也有對它的研究,儘管在一個圖中尋找給定大小的團達到了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_graph2-連通分量英語Biconnected_component為團。
  • 弦圖的點具有完美消去序(perfect elimination ordering),這種排序具有如下性質:對於所有的點中排序在後的點和共同構成一個團。
  • Cograph英語Cograph的所有導出子圖具有如下性質:任意極大團與任意極大獨立集英語Maximal_independent_set有且僅有一個共同點。
  • Interval graph英語Interval_graph的極大團可以按照如下方式排序:對於任意點包含的團在排序中是連續的。
  • 線圖的邊能被一些沒有公共邊的團所覆蓋,並且每個點恰好屬於兩個團。
  • 完美圖英語Perfect_graph的所有導出子圖的團數等於色數
  • Split graph英語Split_graph包含具有如下性質的團:對於圖中每條邊,至少包含一個頂點。
  • Triangle-free graph英語Triangle-free_graph的團數至多為2。

相關定理

  • 圖蘭定理給出了稠密圖中團的大小的下界。[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

注釋

參考文獻

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.