图兰定理 - 维基百科,自由的百科全书
此條目需要擴充。 (2007年9月26日) |
图兰定理是一個图论中的定理,關於 Kr+1 免除圖的邊數。簡而言之,在所有 n 點且不包(r+1)-點團的圖中,邊數最多的圖是圖蘭圖,而且只有圖蘭圖達到邊數的最大值。圖蘭圖是將 n 點分成大小差不多的r 部分,兩點再向一部份若且惟若兩點之間有連邊。
圖蘭定理於1941年首次由匈牙利數學家圖蘭·帕爾(Turán Pál)發現,但 r=2 的情形早在 1907 年由 Mantel 提出。
敘述
[编辑]若 G 是一個有 n 點的圖,而且完全图 Kr+1 不是 G 的子圖,則 G 最多有條邊。此外,如果 G 有條邊,則 G 一定是圖蘭圖 。
圖蘭圖
[编辑]定義
[编辑]圖蘭圖 的定義為一個特殊的具有 n 點的完全r-分圖,其中各部份的頂點數的差不超過1,或者說,r 個部份分別有個頂點。
性質
[编辑]在所有具有 n 點的 r-分圖中,圖蘭圖 是唯一一個边數最多的圖。
證明
假設 K 是一個边數最多的 r-分圖,那麼很明顯的,K 是一個完全 r-分圖。
假設 K 的 r 個部份的點集中,有 U、V 兩部分滿足 ,定義 K' 為取出 K 中 U 的一個點 x,移動到 V 之中,並且刪除所有原本 x 與 V 中的點的連邊,然後將 x 與所有 U 中的點連邊,於是,K' 仍然是一個完全 r-分圖,且經過此操作,有 。因此,K' 比 K 有更多的邊,產生矛盾。因此,r-分圖 K 的各部分點集的頂點數至多差 1,即 K 是圖蘭圖 。
定理證明
[编辑]對於 r 做數學歸納法,當 r=0,不存在 K2 子圖,即沒有邊,因此 G 一定是「完全一分圖」,G 的頂點集形成一個獨立集。
對一般的正整數 r,若 G 是一個有 n 點的圖,而且完全图 Kr+1 不是 G 的子圖,則考慮 G 中度數最大的點 x,設 為 x 的所有鄰居所形成的集合,設 G' 為的導出子圖,因此 Kr 不是 G' 的子圖,否則該 Kr 加上點 x 是 G 的一個 Kr+1 子圖。
由歸納法假設,G' 的邊數不超過圖蘭圖的邊數,定義 H 是一個完全 r-分圖,包含 H' 和另外 |G|-|G'| 個點,這些點互相不相鄰,並和所有 H' 中的點相鄰。於是有
其中,第一個不等號成立是因為其右邊將兩端點都在 V(G)-V(G') 的邊算了兩次,其餘的邊算了一次。故圖蘭圖是所有滿足條件的圖中邊數最多的之一。
最後,當等式成立時,G 在 V(G)-V(G') 中沒有邊,且 G' 與圖蘭圖 H' 有一樣多的邊,尤歸納法假設知道,G' 同構於 H'。因此 G 是一個 r-分圖,V(G)-V(G') 是其中的一部分。由於圖蘭圖是多分圖中唯一邊數最多的,因此 G 是圖蘭圖 ,得證。
參見
[编辑]
|