查看“︁图兰定理”︁的源代码

{{expand|time=2007-09-26T20:09:51Z}}

'''图兰定理'''是一個[[图论]]中的定理，關於 K<sub>r+1</sub> 免除圖的邊數。簡而言之，在所有 n 點且不包(r+1)-[[團 (圖論)|點團]]的圖中，邊數最多的圖是[[圖蘭圖]]，而且只有圖蘭圖達到邊數的最大值。圖蘭圖是將 n 點分成大小差不多的r 部分，兩點再向一部份若且惟若兩點之間有連邊。

圖蘭定理於1941年首次由匈牙利數學家[[圖蘭·帕爾]]（Turán Pál）發現，但 r=2 的情形早在 1907 年由 Mantel 提出。

== 敘述 ==
若 G 是一個有 n 點的圖，而且完全图 K<sub>r+1</sub>  不是 G 的子圖，則 G 最多有<math>\frac{r-1}{r}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}</math>條邊。此外，如果 G 有<math>\left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}</math>條邊，則 G 一定是圖蘭圖 <math>T_{n,r}</math>。

== 圖蘭圖 ==
=== 定義 ===
圖蘭圖 <math>T_{n,r}</math> 的定義為一個特殊的具有 n 點的[[多分圖|完全r-分圖]]，其中各部份的頂點數的差不超過1，或者說，r 個部份分別有<math>\left \lfloor\frac{n}{r}\right \rfloor,\left \lfloor\frac{n+1}{r}\right \rfloor, \dots,\left \lfloor\frac{n+r-1}{r}\right \rfloor</math>個頂點。
=== 性質 ===
在所有具有 n 點的 r-分圖中，圖蘭圖 <math>T_{n,r}</math>是唯一一個边數最多的圖。

'''證明'''

假設 K 是一個边數最多的 r-分圖，那麼很明顯的，K 是一個完全 r-分圖。

假設 K 的 r 個部份的點集中，有 U、V 兩部分滿足 <math>|U| \geq |V|+2</math>，定義 K' 為取出 K 中 U 的一個點 x，移動到 V 之中，並且刪除所有原本 x 與 V 中的點的連邊，然後將 x 與所有 U 中的點連邊，於是，K' 仍然是一個完全 r-分圖，且經過此操作，有 <math>|E(K')|=|E(K)|+(|U|-1)-|V|\geq |E(K)|+1</math>。因此，K' 比 K 有更多的邊，產生矛盾。因此，r-分圖 K 的各部分點集的頂點數至多差 1，即 K 是圖蘭圖 <math>T_{n,r}</math>。

== 定理證明 ==
對於 r 做數學歸納法，當 r=0，不存在 K<sub>2</sub> 子圖，即沒有邊，因此 G 一定是「完全一分圖」，G 的頂點集形成一個[[獨立集]]。

對一般的正整數 r，若 G 是一個有 n 點的圖，而且完全图 K<sub>r+1</sub> 不是 G 的子圖，則考慮 G 中度數最大的點 x，設 <math>N(x)</math>為 x 的所有鄰居所形成的集合，設 G' 為<math>N(x)</math>的導出子圖，因此 K<sub>r</sub> 不是 G' 的子圖，否則該 K<sub>r</sub> 加上點 x 是 G 的一個 K<sub>r+1</sub> 子圖。

由歸納法假設，G' 的邊數不超過圖蘭圖<math>H':=T_{|G'|,r-1}</math>的邊數，定義 H 是一個完全 r-分圖，包含 H' 和另外 |G|-|G'| 個點，這些點互相不相鄰，並和所有 H' 中的點相鄰。於是有

<math>|E(G)|
\leq\sum_{v\in V(G)-V(G')} \deg_G(v)+|E(G')|
\leq (|G|-|G'|)\deg_G(x)+|E(G)|
=|E(H')|
\leq|E(T_{n,r})| </math>

其中，第一個不等號成立是因為其右邊將兩端點都在 V(G)-V(G') 的邊算了兩次，其餘的邊算了一次。故圖蘭圖是所有滿足條件的圖中邊數最多的之一。

最後，當等式成立時，G 在 V(G)-V(G') 中沒有邊，且 G' 與圖蘭圖 H' 有一樣多的邊，尤歸納法假設知道，G' 同構於 H'。因此 G 是一個 r-分圖，V(G)-V(G') 是其中的一部分。由於圖蘭圖是多分圖中唯一邊數最多的，因此 G 是圖蘭圖 <math> T_{n,r} </math>，得證。

== 參見 ==
* [[艾狄胥－斯通定理]]——圖蘭定理的推廣，將禁止[[完全圖|完全子圖]]改為禁止[[圖蘭圖|圖蘭子圖]]。

{{圖論}}
[[Category:图论]]
[[Category:数学定理|T]]