图兰图

~$\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)$