團 (圖論)
在圖論領域的一個無向圖中,滿足兩兩之間有邊連接的頂點的集合,被稱為該無向圖的團。團是圖論中的基本概念之一,用在很多數學問題以及圖的構造上。計算機科學中也有對它的研究,儘管在一個圖中尋找給定大小的團達到了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的二分維數是指覆蓋G中所有邊所需要的最少的二分團的數目,其中二分團(biclique)就是完全二分子圖 。而分團覆蓋問題 (Clique cover problem)所關心的是用最少的團去覆蓋G中所有的頂點。
相關性質
編輯- Cluster graph的連通分量為團。
- Block graph的2-連通分量為團。
- 弦圖的點具有完美消去序(perfect elimination ordering),這種排序具有如下性質:對於所有的點 , 中排序在 後的點和 共同構成一個團。
- Cograph的所有導出子圖具有如下性質:任意極大團與任意極大獨立集有且僅有一個共同點。
- Interval graph的極大團可以按照如下方式排序:對於任意點 包含 的團在排序中是連續的。
- 線圖的邊能被一些沒有公共邊的團所覆蓋,並且每個點恰好屬於兩個團。
- 完美圖的所有導出子圖的團數等於色數。
- Split graph包含具有如下性質的團:對於圖中每條邊,至少包含一個頂點。
- Triangle-free graph的團數至多為2。
相關定理
編輯- 圖蘭定理給出了稠密圖中團的大小的下界。[2]如果一張圖有足夠多條邊,那麼它肯定包含一個大團。例如,對於任意 階圖,如果它的邊數大於 ,那麼它必然包含一個 階團。
- 拉姆齊定理指出,任意圖或者它的補圖包含這樣的團,它具有至少為對數大小的點數。[3]
- Moon & Moser 指出,階數為 的圖至多有 個極大團。極大值在 Moon-Moser 圖 取得,這是圖蘭圖的在圖蘭定理下的一種極端情況。[4]
- Hadwiger猜想給出了最大團大小與色數之間的關係。
- Erdős–Faber–Lovász猜想給出了圖著色與團之間的關係。
分團問題
編輯在計算複雜性理論中,分團問題(clique problem)在給定圖中尋找最大團的問題。它是圖論中的一個NP完全問題。人們在分團問題上提出了許多算法,指數時間複雜度算法包括Bron–Kerbosch算法,而針對特定一類圖有多項式時間複雜度算法,例如平面圖和完美圖。
注釋
編輯- ^ 其實Kuratowski (1930) 更早提出完全子圖一詞(一個有限圖是平面圖,若且唯若它不包含完全子圖或完全二分子圖),但作者在最初的措辭著意於拓撲術語,而非圖論術語.
- ^ Turán, Paul, On an extremal problem in graph theory, Matematikai és Fizikai Lapok, 1941, 48: 436–452 (匈牙利語)
- ^ Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory , New York: John Wiley and Sons, 1990, ISBN 978-0-471-50046-9
- ^ 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=
值 (幫助).