圖蘭圖

~$\left(1- \frac{1}{r}\right)\frac{n^2}{2}$

$$\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.$$

$$\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.$$

$$\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.$$

$$r$$

$$T(n,r)$$ 圖蘭圖（Turán graph），記作 $T(n,r)$，是一種完全多分圖（complete multipartite graph）：將 $n$ 個頂點分成 $r$ 個部分，各部分大小盡可能相等，若且唯若兩頂點屬於不同部分，則在兩者之間連一條邊。設 $n$ 除以 $r$ 的商為 $q$、餘數為 $s$（即 $n = qr + s$），則此圖具有 $K_{q+1, q+1, \ldots, q, q}$ 的形式，其邊數為

$\left(1 - \frac{1}{r}\right)\frac{n^2 - s^2}{2} + {s \choose 2}$。

當 $r\le7$ 時，邊數亦可簡寫為 $\left\lfloor\left(1-\frac1r\right)\frac{n^2}2\right\rfloor$。圖中有 $s$ 個大小為 $q+ 1$ 的部分，以及 $r - s$ 個大小為 $q$ 的部分；每個頂點的度為 $n-q-1$ 或 $n-q$。若 $n$ 可被 $r$ 整除（即 $s=0$），則圖蘭圖是正則圖。

## 圖蘭定理

圖蘭圖以匈牙利數學家圖蘭·帕爾命名，他用此圖證明圖蘭定理，這是極值圖論中的重要結果。

由鴿巢原理可知，圖蘭圖中任意 $r+1$ 個頂點必含同屬某一部分的兩個頂點，因此圖蘭圖不含大小為 $r+1$ 的團。根據圖蘭定理，在所有 $n$ 個頂點、不含 $(r+1)$-團的圖中，圖蘭圖的邊數最多。Keevash 與 Sudakov（2003）還證明：若 $\alpha$ 充分接近 1，則圖蘭圖也是唯一滿足「任意 $\alpha n$ 個頂點之匯出子圖，其邊數至少為 $\frac{r-1}{3r}(2\alpha -1)n^2$」的 $(r+1)$-團自由 $n$ 階圖。艾狄胥－斯通定理將圖蘭定理推廣至禁止固定圖蘭圖作為子圖的情形，並依被禁止子圖的色數，給出極值圖論中的一般界（詳見下文「極值性質」）。

## 圖蘭定理的證明

### 特例：Mantel 定理（$r=2$）

Mantel 定理：$n$ 頂點的 $K_3$-自由圖最多有 $\lfloor n^2/4\rfloor$ 條邊，等號成立若且唯若圖為 $T(n,2)$。

證明：設 $G$ 為 $K_3$-自由，取度最大的頂點 $v$。$N(v)$ 為獨立集，故 $G$ 的邊只連接 $N(v)$ 與 $V\setminus N(v)$；$V\setminus N(v)$ 內無邊。因 $\deg(v)$ 最大，$|N(v)|\ge |V\setminus N(v)|$，故 $|E(G)|\le |N(v)||V\setminus N(v)|\le \lfloor n^2/4\rfloor$，等號時得 $T(n,2)$。

### 一般情形：Zykov 對稱化

圖蘭定理：若 $G$ 為 $n$ 頂點、$K_{r+1}$-自由圖，則 $|E(G)|\le |E(T(n,r))|$，等號成立若且唯若 $G\cong T(n,r)$。

證明概要（Zykov, 1949）：設 $G$ 為邊數極大的 $K_{r+1}$-自由圖。若存在非邊 $\{u,v\}$ 且 $N(u)\not\subseteq N(v)$，Zykov 對稱化：將 $u$ 的鄰居改為與 $v$ 相鄰，不減邊數且不產生 $K_{r+1}$。重複後 $\overline{G}$ 為 $r$ 個團的不相交並，各團大小至多相差 1，故 $G\cong T(n,r)$。Turán 原始證明用不同方法；詳見 Bollobás。

## 極值性質

### 記法

本文記 $T(n,r)$ 為將 $n$ 個頂點分成 $r$ 個大小盡可能相等的部分後，形成的完全 $r$-分圖；此圖不含 $K_{r+1}$。許多教科書（如 Diestel）則以 $T_s(n)$ 表示完全 $s$-分圖（即 $s$ 個部分），用以描述禁止 $K_{s+1}$ 的極值問題，例如 $T(n,r)=T_r(n)$。閱讀文獻時須留意下標是指「部數」還是「被禁止團的大小減 1」。

在極值圖論中，若 $H$ 為固定圖，$\mathrm{ex}(n,H)$ 表示所有 $n$ 頂點、不含 $H$ 之子圖的圖中，邊數的最大值。圖蘭定理（Turán, 1941）斷言

$\mathrm{ex}(n,K_{r+1}) = |E(T(n,r))| = \left(1 - \frac{1}{r}\right)\frac{n^2 - s^2}{2} + {s \choose 2}$。

其中 $n=qr+s$（$0\le s<r$）。且達到此上界的 $K_{r+1}$-自由圖必同構於 $T(n,r)$。

### 補圖結構

圖蘭圖 $T(n,r)$ 的各個部分在圖中為獨立集，故其補圖 $\overline{T(n,r)}$ 為 $r$ 個團的不相交並，各團大小至多相差 1。Zykov（1949）的對稱化（symmetrization）結構性證明表明：若 $G$ 為 $K_{r+1}$-自由且邊數極大（再加任一非邊即出現 $K_{r+1}$），則 $\overline{G}$ 必為若干團的不相交並；在 $n$ 固定時，這些團的大小分配與 $T(n,r)$ 相同，從而 $G\cong T(n,r)$。

### 圖蘭密度（Turán density）

當 $n\to\infty$ 時，$T(n,r)$ 的（漸近）邊密度為

$$\frac{|E(T(n,r))|}{\binom{n}{2}} \longrightarrow 1 - \frac{1}{r} = \frac{r-1}{r}.$$

更一般地，Erdős–Simonovits 定理指出：對任意色數 $\chi(H)=r+1$ 的圖 $H$。

$$\lim_{n\to\infty}\frac{\mathrm{ex}(n,H)}{\binom{n}{2}} = \frac{\chi(H)-2}{\chi(H)-1} = \frac{r-1}{r}.$$

因此禁止 $K_{r+1}$ 時，$T(n,r)$ 不僅邊數最多，也決定了這類極值問題的漸近密度；圖蘭圖可視為該密度的達界範例。

### 色數與緊性

$T(n,r)$ 的色數為 $r$，團數 $\omega(T(n,r))=r$（各部分內無邊，部分間完全連接）。在所有 $n$ 頂點、色數至多為 $r$（等價地，不含 $K_{r+1}$）的圖中，$T(n,r)$ 的邊數最大；若再新增任一非邊，則必出現 $K_{r+1}$ 子圖，故該上界是緊的。

### 略增邊數的後果

圖蘭圖已相當稠密：邊數約為 $\frac{r-1}{2r}n^2$。艾狄胥－斯通定理（Erdős–Stone, 1946）表明，對任意 $\varepsilon>0$ 與 $t\ge 1$，當 $n$ 充分大時，任一 $n$ 頂點、邊數至少為 $|E(T(n,r))|+\varepsilon n^2$ 的圖，必含 $K_{r+1}(t)$（即各部恰有 $t$ 個頂點的完全 $(r+1)$-分圖）作為子圖。換言之，只要比圖蘭圖多出 $\Theta(n^2)$ 條邊，就不僅出現 $K_{r+1}$，還會出現任意大的完全 $(r+1)$-分圖副本。

### 特例：Mantel 定理

$r=2$ 時，$T(n,2)$ 為邊數最多的 $K_3$-自由圖，即完全二分圖且兩部大小相差至多 1。此結果早於圖蘭定理，由 Mantel（1907）證明；圖蘭定理可視為其對一般 $K_{r+1}$ 的推廣。

## 特殊情形

<image>

當參數 $r$ 取某些特定值時，圖蘭圖即為文獻中另行研究的重要圖族。

圖蘭圖 $T(2n,n)$ 可視為從完全圖 $K_{2n}$ 中刪去一組完美匹配而得。Roberts（1969）證明此圖的盒維數恰為 $n$，有時稱為 Roberts 圖。它也是 $n$ 維正交多面體的一維骨架；例如 $T(6,3)=K_{2,2,2}$ 即正八面體圖。若 $n$ 對情侶參加聚會，每人與除伴侶外的所有人握手，則握手關係恰構成此圖，故亦稱雞尾酒會圖（cocktail party graph）。

圖蘭圖 $T(n,2)$ 是完全二分圖；當 $n$ 為偶數時，它還是 Moore 圖。當 $r$ 整除 $n$ 時，圖蘭圖是對稱圖，也是強正則圖；不過部分作者將圖蘭圖視為強正則的平凡情形，因而從定義中排除。

圖蘭圖類可具有指數級數量的極大團（maximal cliques）。例如 $T(n,\lceil n/3\rceil)$ 有 $3^a 2^b$ 個極大團，其中 $3a+2b=n$ 且 $b\le 2$；每個極大團由從各部分各取一頂點構成。這是任意 $n$ 頂點圖中極大團數的上界，此類圖有時稱為 Moon–Moser 圖。

## 其他性質

每個圖蘭圖都是cograph：可由孤立頂點經有限次不相交並與補圖運算得到。具體而言，可先將圖蘭圖的各獨立集表為孤立頂點的不相交並，再取各獨立集補圖的不相交並之補圖。

Chao 與 Novacky（1982）證明，圖蘭圖在色多項式意義下是唯一的：不存在其他圖與其具有相同色多項式。Nikiforov（2005）以圖蘭圖給出圖及其補圖前 $k$ 個特徵值之和的下界。

Falls、Powell 與 Snoeyink（2003）在基因組資料中，將資料表示為圖並搜尋大型圖蘭子圖，以有效辨識直系同源基因群。

在幾何圖論中，Pór 與 Wood（2005）證明圖蘭圖任意三維格點嵌入的體積為 $\Omega((rn)^{3/4})$。Witsenhausen（1974）猜想：在 $\mathbb{R}^d$ 中，直徑為 1 的 $n$ 點配置，其平方距離和的最大值，會在將圖蘭圖嵌入正則單形頂點時達到。

$n$ 頂點圖 $G$ 是圖蘭圖 $T(n,r)$ 的子圖，若且唯若 $G$ 存在 $r$ 色的公平著色（equitable coloring）。圖蘭圖按獨立集的分劃，對應 $G$ 按色類的分劃；因此，圖蘭圖是具有 $r$ 色公平著色的唯一極大 $n$ 頂點圖。

## 外部連結

- MathWorld：Turán Graph
- 國家教育研究院樂詞網（兩岸數學名詞對照）

## 基本資料

- 說明：圖蘭圖 T(13,4)
- 得名自：圖蘭·帕爾
- 頂點：$n$
- 邊：~$\left(1- \frac{1}{r}\right)\frac{n^2}{2}$
- 半徑：$\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.$
- 直徑：$\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.$
- 圍長：$\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.$
- 色數：$r$
- 記號：$T(n,r)$