k部图与图兰定理

摘要: k部图的应用

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

二部图是应用非常广泛的一类图。相关的理论研究的非常多，很多业务场景可以抽象为二部图上的匹配问题。而 k 部图在定义上与 2 部图类似，但由于应用比二部图少，相对来说见的会少一些。k 部图有个重要的应用是推导图兰定理。

图兰定理 1941 年首次由匈牙利数学家图兰·帕尔发现，但 k=2 的情形早在 1907 年由 Mantel 提出。

图兰定理可以用来解决一些图论中的最优化问题，比如最大独立集问题、最小顶点覆盖问题等。在实际应用中，我们可以通过图兰定理来估算一个图中最大独立集的大小。

例如在社交网络中，我们可以将用户之间的关系表示为一个图，其中每个用户对应一个顶点，用户之间的关系对应一条边。在这个图中，通过图兰定理可以估算出最大独立集的大小，从而为我们设计社交网络推荐算法提供参考。

本文我们首先介绍 k 部图上的边的计数的结论，然后推导图兰定理，最后推导出独立集大小的下界。

---

k 部图

$G$ 是简单图，其顶点集为 $V(G)$。若 $V$ 可以划分为 $k$ 个非空子集 $V_{i}, i=1,2,\cdots,k$，使得对 $\forall uv\in E(G)$，有 $u \in V_{i}, v\in V_{j}, i\neq j$。则称 $G$ 为 $k$ 部图。

$V = \bigcup\limits_{i=1}\limits^{k}U_{i}, V_{i}\cap V_{j}=\varnothing, i\neq j$ 称为 $G$ 的一个 $k$ 部划分。

若 $\forall i\neq j$，对 $\forall u\in V_{i}, v\in V_{j}$，有 $uv \in E$，则称 $G$ 为完全 k 部图，记为 $K_{n_{1}, n_{2}\cdots, n_{k}}$。若 $k$ 部划分中每个集合均为 $n$ 个节点，则完全 $k$ 部图可以记为 $K_{n}(k)$。

完全 $k$ 部图边数的上界，以及 $K_{n}(k)$ 的边数，可以从图兰图中推导出来。

图兰图

记 $T_{k, v}$ 为每个划分有 $m=\lfloor\frac{v}{k}\rfloor$ 或 $n=\lceil\frac{v}{k}\rceil$ 个顶点的完全 $k$ 部图。也就是具有 $v$ 个顶点的完全 $k$ 部图，且 $k$ 部划分的各个部分的顶点数的差均不超过 1。称为图兰图。

下图是 $T_{4,13}$ 的例子：

令 $v = km + r$，$0 \leq r < k$，则 $r = v - km$。

由 $T_{k,v}$ 的定义，$k$ 部划分中，有 $r$ 个具有 $m+1$ 个顶点，$k-r$ 个具有 $m$ 个顶点。由 $k$ 部图的定义：

$$\begin{align} \epsilon(T_{k,v}) &= \binom{v}{2} - r\binom{m+1}{2} - (k-r)\binom{m}{2} \\ &= \frac{1}{2}(v(v-1) - rm(m+1) - (k-r)m(m-1)) \\ &= \frac{1}{2}(v-m)(v-m-1) + \frac{1}{2}(k-1)m(m+1) \\ &= \binom{v-m}{2} + (k-1)\binom{m+1}{2} \end{align}$$

于是我们得到了图兰图 $T_{k, v}$ 的边数：

$$\epsilon(T_{k,v}) = \binom{v-m}{2} + (k - 1)\binom{m + 1}{2}, \quad m = \left\lfloor\frac{v}{k}\right\rfloor$$

令 $v = kn$，$T_{k,v}$ 就是各个划分均为 $n=\frac{v}{k}$ 的完全 k 部图 $K_{n}(k)$，代入后得到 $K_{n}(k)$ 的边数：

$$\epsilon(K_{n}(k)) = \binom{kn-n}{2} + (k-1)\binom{n+1}{2} = \frac{1}{2}k(k-1)n^{2}$$

---

定理(完全k部图边数上界)：$v$ 阶完全 $k$ 部图 $G$，$\epsilon(G) \leq \epsilon(T_{k,v})$，当且仅当 $G\cong T_{k, v}$ 时等号成立。

---

证明 (反证)

$G = K_{n_{1}, n_{2},\cdots,n_{k}}$ 是具有最大边数的完全 k 部图。由完全 k 部图的定义：

$$\epsilon(G) = \binom{v}{2} - \sum\limits_{l=1}\limits^{k}\binom{n_{l}}{2}$$

假设 $G \not\cong T_{k,v}$，则 $\exists i < j$ 使得 $n_{i} - n_{j} > 1$。考虑另一个完全 $k$ 部图 $G’$，其各个部分的顶点数分别为：

$$n_{1}, \cdots, n_{i-1}, n_{i}-1, n_{i+1},\cdots, n_{j-1}, n_{j}+1, n_{j+1},\cdots,n_{k}$$ $$\begin{align} \epsilon(G') &= \binom{v}{2} - \sum\limits_{l=1\atop l\neq i,j}\limits^{k}\binom{n_{l}}{2} - \binom{n_{i} - 1}{2} - \binom{n_{j} - 1}{2} \\ &= \binom{v}{2} - \sum\limits_{l=1\atop l\neq i,j}\limits^{k}\binom{n_{l}}{2} - \binom{n_{i}}{2} - \binom{n_{j}}{2} + (n_{i} - n_{j} - 1) \\ &= \binom{v}{2} - \sum\limits_{l=1}\limits^{k}\binom{n_{l}}{2} + (n_{i} - n_{j}) - 1 \\ &> \binom{v}{2} - \sum\limits_{l=1}\limits^{k}\binom{n_{l}}{2} = \epsilon(G) \\ \end{align}$$

这与“G 是具有最大边数的完全 k 部图”矛盾。所以完全 k 部图 $G$ 取得最大边数时有 $G \cong T_{k,v}$。即：

$v$ 阶完全 $k$ 部图 $G$ 有 $\epsilon(G) \leq \epsilon(T_{k,v})$，当且仅当 $G\cong T_{k, v}$ 时等号成立。$\Box$

---

定理(图兰图边数的界)：

$$(1 - \frac{1}{k})\binom{v-1}{2} \leq \epsilon(T_{k, v}) \leq (1 - \frac{1}{k})\frac{v^{2}}{2}$$

---

将 $\epsilon(T_{k,v})$ 的公式展开，代入 $v = km + r$ 得：

$$\epsilon(T_{k,v}) - (1 - \frac{1}{k})\binom{v-1}{2} = \frac{r^{2}-r+m(k^{2}-k)}{2k}$$

由于 $r, k\geq 0$，于是整数 $(r^{2} - r) \geq 0$、$(k^{2} - k) \geq 0$，因此 $\frac{r^{2}-r+m(k^{2}-k)}{2k} \geq 0$.

另一方面，将 $\epsilon(T_{k,v})$ 展开:

$$\begin{align} \epsilon(T_{k,v}) &= \binom{v-m}{2} + (k - 1)\binom{m + 1}{2}, \quad m = \left\lfloor\frac{v}{k}\right\rfloor \\ &= \frac{1}{2}(v^{2} - v -2mv + km^{2} + km) \end{align}$$

将 $m = \lfloor\frac{v}{k}\rfloor$ 代入：

$$\epsilon(T_{k,v}) = \frac{1}{2}(v^{2} - v -2v\lfloor\frac{v}{k}\rfloor +k(\lfloor\frac{v}{k}\rfloor)^{2} +k\lfloor\frac{v}{k}\rfloor)$$

若 $k\mid v$，则 $\lfloor\frac{v}{k}\rfloor = \frac{v}{k}$，于是 $\epsilon(T_{k,v}) = \frac{(k-1)n^{2}}{2k}$

下面考虑 $k\not\mid v$ 的情况。令 $v = km + r$，$0\leq r < k$，于是：

$$\begin{align} \epsilon(T_{k,v}) &= \frac{1}{2}((km+r)^{2} - (km+r) -2m(km+r) + km^{2} + km) \\ &= \frac{k^{2}m^{2}}{2} + kmr + \frac{r^{2}}{2} - \frac{r}{2} - \frac{km^{2}}{2} - mr \end{align}$$

记上式为 $a = \epsilon(T_{k,v})$，同时记 $b = (1 - \frac{1}{k})\frac{v^{2}}{2} = \frac{k^{2}m^{2}}{2} + \frac{r^{2}}{2} + kmr - mr - \frac{km^{2}}{2} - \frac{r^{2}}{2k}$。

$$b - a = \frac{r(k-r)}{2k}$$

由于 $r \geq 0, k > r \geq 0$，$b \geq a$，因此：

$$(1 - \frac{1}{k})\binom{v-1}{2} \leq \epsilon(T_{k, v}) \leq (1 - \frac{1}{k})\frac{v^{2}}{2}$$

$\Box$

由完全k部图边数上界的定理，以及图兰图边数的界的定理，我们实际上已经几乎推导出了图兰定理。

---

图兰定理

图兰定理刻画了含有 $v$ 个顶点且不含大小为 $k+1$ 的团的简单图的最大边数。考虑以下问题。

若 $G$ 为简单图，有 $v$ 个顶点，不包含 $k+1$ 团，也就是完全图 $K_{k+1}$ 不是 $G$ 的子图。对于这样的图 $G$ 最多有多少条边。

图兰定理说明了，$\epsilon(G) \leq (1 - \frac{1}{k})\frac{v^{2}}{2}$。

定理(图兰)：设 $G$ 是 $v$ 个顶点的简单图，若 $G$ 不包含完全图 $K_{k+1}$，则：

$$\epsilon(G) \leq \epsilon(T_{k,v}) \leq (1 - \frac{1}{k})\frac{v^{2}}{2}$$

---

证明：右半部分前面已经证明。下面证明左半部分。

下面证明简单图 $G$ 不含 $k+1$ 的团，则 $G$ 取到边数最大的图一定是 $T_{k,v}$。

考虑 $G$ 为取到边数最大的图，首先我们证明引理：$G$ 中不含三个顶点 $u, v, w$ 使得 $vw\in E, uv\notin E, uw \notin E$。

case1：若 $d(u) < d(v)$ 或 $d(u) < d(w)$，不妨设 $d(u) < d(v)$，那么将 $v$ 复制，得到 $v’$，使得 $v’$ 的邻居与 $v$ 相同。然后删除 $u$ 以及 $u$ 关联的边，得到新图 $G’$。则 $G’$ 也是不含 $K_{k+1}$ 的图，但 $\epsilon(G’) = \epsilon(G) + d(v) - d(u) > \epsilon(G)$，这与 $G$ 的边数最多矛盾。

case2：若 $d(u) \geq d(v)$ 且 $d(u) \geq d(w)$，则将 $u$ 复制两次得 $u’$、$u’’$，使得新的两个点的邻居与 $u$ 相同，删除 $v$，$w$，及其关联的边。则新生成的图 $G’$ 也不含 $K_{k+1}$，但 $\epsilon(G’) = \epsilon(G) + 2d(u) - d(v) - d(w) + 1 > \epsilon(G)$，与 $G$ 的边数最多矛盾。

于是：$G$ 中不含三个顶点 $u, v, w$ 使得 $vw\in E, uv\notin E, uw \notin E$。这说明 $uv \notin E(G)$ 具有传递性，因此是一个等价关系。

因此可以根据 $uv \notin E$ 将 G 的顶点划分为等价类。即，如果两个顶点不相邻，则它们在同一个等价类中。这意味着 G 是一个完全多部图。假设 $G$ 是一个完全 $p$ 部图。

另一方面，$G$ 无 $K_{k+1}$，则 $G$ 边数取最大时一定包含 $K_{k}$，因为如果不含 $K_{k}$，则可以通过加边的方式得到一个 $K_{k}$。而 $K_{k}$ 是一个 $k$ 部图。因此 $G$ 是一个完全 $k$ 部图。

由完全 $k$ 部图边数上界定理，有 $\epsilon(G) \leq T_{k,v}$。 $\Box$

Mentel 定理

在图兰定理中，取 $k=2$，即得 Mentel 定理。

定理(Mentel)：顶点数为 $v$ 且不包含三角形的简单图最多有 $\lfloor\frac{v^{2}}{4}\rfloor$

极值图论

极值图论主要研究图的各种不变量，例如顶点数、边数、连通度、最小度、最大度、围长、色数、直径等，研究为了使得图具有某些特定性质，不变量之间应满足的关系。

对一类图 $\mathcal{H}$，给定性质 $\mathcal{P}$ 以及不变量 $\mu$，我们希望找到最小的 $m$，使得 $\mathcal{H}$ 中满足 $\mu > m$ 的图 $G$ 都具有性质 $\mathcal{P}$。$\mathcal{H}$ 中满足 $\mu = m$ 的不具有性质 $\mathcal{P}$ 的图称为此性质的极图。

例如给定顶点数 $n$，边数至少为 $n$ 的连通图都包含圈。图类为 $\mathcal{H}$ 是顶点数为 $n$ 的连通图，不变量 $\mu$ 为边数，性质 $\mathcal{P}$ 为含圈，树为极图。

禁用子图问题

禁用子图问题是一类极值问题。给定简单图 $F$，记 $\mathrm{ex}(v, F)$ 表示顶点数为 $v$，不包含子图 $F$ 的简单图具有的最大边数。

当 $v \geq k + 1 \geq 2$ 时，就是本文研究的问题，即 $\mathrm{ex}(v, K_{k+1}) = \epsilon(T_{k,v})$。图类 $\mathcal{H}$ 为顶点数为 $n$ 的简单图。不变量 $\mu$ 为边数，性质 $\mathcal{P}$ 为不包含子图 $K_{k+1}$。

要找最小的 $m$，使得 $\mu > m$ 时 $G$ 不具有性质 $\mathcal{P}$ 也就是包含子图 $K_{k+1}$。图兰定理给出了 $m$，并且 $\mu = m$ 时唯一的极图是图兰图 $T_{k, v}$。

---