在圖論中，圖蘭定理（Turán's theorem）給出了不包含特定大小完全子圖（克里克，Clique）的無向圖中，邊數的最大上界。它是極值圖論（Extremal graph theory）的核心結果之一。極值圖論主要研究滿足給定性質的最大或最小圖，而圖蘭定理則是（Forbidden subgraph problem）中禁止特定完全子圖的一個特例。
一個不包含 (r+1) 個頂點的完全圖 K_{r+1} 的 n 頂點圖的例子可以這樣構造：將 n 個頂點分成 r 個大小相等或儘可能相等的集合，若兩個頂點屬於不同的集合，則在它們之間連一條邊。這樣得到的圖稱為圖蘭圖（Turán graph）T(n,r)。圖蘭定理指出，在所有不含 K_{r+1}（即 K_{r+1}-free）的 n 頂點圖中，圖蘭圖擁有的邊數最多。
圖蘭定理及其極端情況的圖蘭圖，最早由匈牙利數學家圖蘭·帕爾（Pál Turán）於 1941 年提出並研究。
}}
评论 (0)