團 (圖論)
在圖論領域的一個無向圖中，滿足兩兩之間有邊連接的頂點的集合，被稱為該無向圖的團。團是圖論中的基本概念之一，用在很多數學問題以及圖的構造上。計算機科學中也有對它的研究，儘管在一個圖中尋找給定大小的團達到了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中所有的頂點。
獨立集是剛好和團相反的概念，因為圖G中的團和圖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=值 (幫助).