Bóna · 枚举与解析组合学导论 · 第 6 章 极值组合学

6.1　极值图论Extremal graph theory

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

现实生活中充满了最优化问题（optimization problems），也就是说，我们常常要找出完成某项任务的最佳方式。这往往涉及找出在某个特定标准下最好的图。这正是极值图论（extremal graph theory）的主题。

本节目标回答一类形如“在某个限制下，一个有 \(n\) 个顶点的图最多能有多少条边”的问题。我们会依次解决三个具体限制：(1) 图是二部图（没有奇圈）；(2) 图不含三角形；并指出更一般的方向。核心工具只有一件：算术–几何平均不等式 \(\sqrt{xy}\le\frac{x+y}{2}\)。

6.1.1　二部图

在上一章里，我们见过这样的图：它的顶点被染上颜色，使得相同颜色的顶点之间没有边。如果只有一种颜色，那么这种染色仅对空图（即没有任何边的图）存在。所以第一个非平凡的情形是我们有两种颜色。这种情形本身就非常有趣，因此它有自己专门的名字。

定义 6.1 称图 \(G\) 为二部图（bipartite），如果它的顶点集存在一个正常的 2-染色（proper 2-coloring），即用两种颜色给顶点染色，使得任何一条边的两个端点颜色不同。

二部图在日常生活中比比皆是。例如，设想一家公司有若干空缺职位，又有若干应聘者。一名应聘者可能胜任不止一个职位，一个职位也可能吸引不止一名应聘者。可以用一个二部图来表示这一情形：红色顶点代表职位，蓝色顶点代表应聘者，当某蓝色顶点对应的应聘者能胜任某红色顶点对应的职位时，就在这两个顶点之间连一条边。这样的定义保证了相同颜色的顶点之间不会有边，因此得到的图是二部图。

职位（红） 应聘者（蓝）
所有边都横跨红、蓝两侧；同色顶点之间没有边，这正是二部图的特征。

二部图也可以不借助颜色来定义，依据的是下面这个事实。

命题 6.2 图 \(G\) 是二部图，当且仅当它不含奇数长度的圈（odd cycle）。
证明. 设 \(G\) 是二部图，并设 \(f\) 是 \(G\) 顶点的一个正常 2-染色。如果 \(G\) 含有一个长度为 \(2k+1\) 的圈 \(C\)，那么 \(C\) 至少含有 \(k+1\) 个同色顶点，于是 \(C\) 中必有两个相邻的同色顶点（与正常染色矛盾）。

反过来，假设 \(G\) 没有奇圈。那么我们从某个顶点 \(V\) 开始染色：把 \(V\) 染成红色，再把它的邻居染成蓝色，再把这些蓝邻居的邻居染成红色，如此继续，直到 \(G\) 的所有顶点都被染色。这一过程总会得到一个正常的 2-染色，因为与 \(V\) 距离为偶数的顶点是红色，距离为奇数的顶点是蓝色。所以，如果在两个同色顶点 \(A\) 与 \(B\) 之间存在一条边，那么 \(G\) 中就会出现一个奇圈。事实上，取从 \(V\) 到 \(A\) 的一条最短路 \(p\)，以及从 \(V\) 到 \(B\) 的一条最短路 \(p'\)。注意 \(A\) 与 \(B\) 到 \(V\) 的距离相等，因为它们相邻且同色。若 \(p\cap p'=\{V\}\)，则路 \(p\)、路 \(p'\) 与边 \(AB\) 的并构成一个奇圈。若不然，设 \(W\) 是 \(p\) 与 \(p'\) 的公共顶点中离 \(V\) 最远的一个。那么 \(A\) 与 \(B\) 到 \(W\) 的距离相等，于是 \(p\) 中位于 \(A\) 与 \(W\) 之间的部分、\(p'\) 中位于 \(B\) 与 \(W\) 之间的部分，连同边 \(AB\)，一起构成一个奇圈。示意见图 6.1。♦

V A B 最短路 p 最短路 p′ 边 AB
图 6.1　如果没有奇圈，那么我们的 2-染色就是正常的。两条等长最短路加上同色端点间的边 \(AB\)，长度为偶+偶+1，是奇数。
例（用具体圈验证命题 6.2） 取一个长度为 \(4\) 的圈 \(C_4\)：顶点 \(1\!-\!2\!-\!3\!-\!4\!-\!1\)。把 \(1,3\) 染红、\(2,4\) 染蓝，每条边都红蓝相连，是二部图，且 \(4\) 是偶数。再取长度为 \(3\) 的圈 \(C_3\)（三角形）\(1\!-\!2\!-\!3\!-\!1\)：无论怎样用两种颜色染 \(3\) 个顶点，必有两个顶点同色，而它们之间恰好有边——所以 \(C_3\) 不是二部图，\(3\) 是奇数。这与命题 6.2 完全吻合。

在继续之前，我们应当澄清“图的子图”指的是什么，因为这个概念对本节余下内容至关重要。这里有两个不同的概念，如下。

定义 6.3 设 \(G\) 是一个图。称图 \(H\) 是 \(G\) 的子图（subgraph），如果 \(H\) 的顶点集是 \(G\) 顶点集的子集，并且 \(H\) 的边集是 \(G\) 边集的子集。

你也许会说：这很合理，但关于定义子图，还有什么好说的呢？下面这个定义——以及它后面的例子——希望能回答这个问题。

定义 6.4 设 \(G\) 是一个图。称图 \(H\) 是 \(G\) 的导出子图（induced subgraph），如果 \(H\) 的顶点集 \(V(H)\) 是 \(G\) 顶点集的子集，并且：当我们取出 \(G\) 中所有连接 \(V(H)\) 内两个顶点的边时，恰好得到 \(H\) 本身。

下面的例子应能阐明这两个概念之间的区别。

例 6.5 图 6.2 中的图 \(G\) 含有若干个与图 \(H\) 同构的子图。事实上，任何由两条边组成的路都是这样一个子图。然而，\(G\) 不含与 \(H\) 同构的导出子图，因为 \(G\) 的任何 \(3\) 顶点导出子图都是 \(K_3\)（三角形）的一份拷贝。
G（三角形 K₃） H（两条边的路）
图 6.2　\(G\) 含有 \(H\) 作为子图（去掉三角形的一条边即得），但不含 \(H\) 作为导出子图——因为只要取出 \(G\) 的任意 \(3\) 个顶点，连着的边自动凑成完整三角形，而不是缺一条边的路。
两种子图的区别（关键）子图：顶点、边都“随便取一部分”，可以扔掉一些边。导出子图：先选定一组顶点，然后原图里这些顶点之间的边一条都不能少，全部保留。所以“路 \(H\)”能作为子图藏在三角形里（扔掉一条边），但不能作为导出子图（选 3 个顶点就必然带上全部 3 条边）。

无论我们采用哪一种子图的定义，都能看出：如果 \(G\) 是二部图，那么 \(G\) 的任何子图或导出子图也是二部图。反过来，如果我们不断向 \(G\) 添加边而不添加新顶点，那么 \(G\) 最终会失去二部性质，因为 \(n\) 个顶点上的完全图 \(K_n\) 在 \(n\ge 3\) 时不是二部图。问题在于：这一转变何时发生？

一方面，树（tree）当然是二部图，因为它没有任何圈，无论偶圈还是奇圈。所以 \(n\) 个顶点上的二部图确实可以有 \(n-1\) 条边。另一方面，由于完全图 \(K_n\) 在 \(n\ge 3\) 时不是二部图，\(n\) 个顶点上的二部图的边数少于 \(\binom{n}{2}\)。那么在 \(n-1\) 与 \(\binom{n}{2}\) 之间，临界点在哪里呢？下面的结果表明，它更接近 \(\dfrac{n^2}{4}\)，而不是 \(n-1\)。

定理 6.6 设 \(n\ge 2\)，\(G\) 是 \(n\) 个顶点上的一个简单二部图。那么 \(G\) 至多有 \(a(n-a)\) 条边，其中 \(a=\lfloor n/2\rfloor\)。

换句话说，\(n\) 个顶点上的二部图的边数不可能超过 \(n^2/4\)。

证明. 设 \(G\) 有 \(a\) 个红色顶点和 \(n-a\) 个蓝色顶点。那么当所有红色顶点都与所有蓝色顶点相邻时，边数达到最大，此时 \(G\) 可以有 \(a(n-a)\) 条边。由初等微积分，函数 \(f(a)=a(n-a)\) 在 \(a=n/2\) 处取得最大值，并且当 \(0n/2\) 时递减。由于 \(a\) 必须是整数，我们的结论得证。♦
例（用 \(n=6\) 算一遍） 取 \(n=6\)，则 \(a=\lfloor 6/2\rfloor=3\)。最大边数 \(=a(n-a)=3\times 3=9\)，恰好等于 \(n^2/4=36/4=9\)。这意味着 \(6\) 个顶点的二部图最多 \(9\) 条边，达到上界的就是把 \(3\) 个红点与 \(3\) 个蓝点两两全连的图 \(K_{3,3}\)。
  1. 把 \(6\) 个顶点分成红、蓝两组，红组 \(a\) 个、蓝组 \(6-a\) 个。
  2. 同色之间不能连边（否则破坏二部性），所以边只能红蓝相连，最多 \(a(6-a)\) 条。
  3. 试各种分法：\(a=1\) 得 \(1\times 5=5\)；\(a=2\) 得 \(2\times 4=8\)；\(a=3\) 得 \(3\times 3=9\)。两边越均匀，乘积越大。
  4. 所以在 \(a=3\)（即对半分）时最大，为 \(9\) 条。♦
完全二部图 K₃,₃：3 红 × 3 蓝 = 9 条边
当左右两侧各 \(3\) 个顶点、两两全连时，达到边数上界 \(9=n^2/4\)。

这里有几点需要补充说明。第一，上面证明中所描述的图——即有 \(a\) 个红顶点、\(n-a\) 个蓝顶点、且所有红顶点都与所有蓝顶点相邻的二部图——称为完全二部图（complete bipartite graph），记作 \(K_{a,\,n-a}\)。例如，图 5.53 所示的图就是 \(K_{2,3}\)。

第二，我们实际证明的，比定理 6.6 的陈述还要多一点。我们不仅证明了这种二部图的边数至多为 \(a(n-a)\)（其中 \(a=\lfloor n/2\rfloor\)），还证明了这个最大值确实能够达到。换句话说，上界 \(a(n-a)\) 无法再改进，因为确实存在 \(n\) 个顶点、边数恰为这么多的二部图。在下文中，我们用“上界 \(a(n-a)\) 是紧的（sharp）”来表述这一事实。

第三，我们还证明了 \(a(n-a)\le n^2/4\) 这一事实，它是几何平均与算术平均之间不等式的直接推论，即不等式 \[\tag{6.1}\sqrt{xy}\le\frac{x+y}{2},\] 它对所有非负实数 \(x\) 与 \(y\) 都成立。我们将多次使用这个不等式。要证明它，注意到两边平方并整理后，它变成不等式 \((x-y)^2\ge 0\)。因为这些步骤是可逆的，所以 (6.1) 成立。现在令 \(x=a\)、\(y=n-a\)，便得到不等式 \(\sqrt{a(n-a)}\le n/2\)，两边平方即 \(a(n-a)\le n^2/4\)。

算术–几何平均不等式的微型证明
  1. 目标：对 \(x,y\ge 0\) 证 \(\sqrt{xy}\le\dfrac{x+y}{2}\)。
  2. 两边都非负，平方等价：\(xy\le\dfrac{(x+y)^2}{4}\)。
  3. 两边乘 \(4\) 并移项：\((x+y)^2-4xy\ge 0\)，即 \(x^2-2xy+y^2\ge 0\)，也就是 \((x-y)^2\ge 0\)。
  4. 完全平方恒 \(\ge 0\)，成立；上述每一步都可逆，故原不等式成立。等号当且仅当 \(x=y\)。♦
代入 \(x=a,\;y=n-a\)（此时 \(x+y=n\)）：\(a(n-a)\le\big(\tfrac{n}{2}\big)^2=\tfrac{n^2}{4}\)，且 \(a=n-a\)（即对半分）时取等。这就解释了为什么前面例子里“两边越均匀，乘积越大”。

不含三角形的图最多有多少边

定理 6.6 表明，如果 \(n\) 个顶点上的图 \(G\) 的边数超过 \(n^2/4\)，那么 \(G\) 必定含有一个奇圈作为子图。

我们断言，能说的远不止于此：在这么多顶点上拥有这么多边的图，甚至会含有一个三角形——从而含有一个非常短的奇圈——作为子图。

定理 6.7 如果 \(n\) 个顶点上的图 \(G\) 含有超过 \(n^2/4\) 条边，那么它含有一个三角形作为子图。

我们向读者发起挑战：用归纳法证明这一事实，然后在习题 1 中核对我们的解答。一个更强、更出人意料的事实（补充习题 4）是：如果 \(2n\) 个顶点上的图 \(G\) 拥有超过 \(n^2\) 条边，那么 \(G\) 必定含有 \(n\) 个三角形！因此，只要 \(G\) 的边数不超过 \(n^2\)，\(G\) 可以一个三角形都没有；可一旦 \(G\) 的边数超过 \(n^2\)，它就突然含有至少 \(n\) 个三角形。

证明（定理 6.7）. 设 \(G\) 是 \(n\) 个顶点上的一个不含三角形的图。让我们尝试调整定理 6.6 的证明，使它给出这个更强的结论。在那个证明里，我们知道图是二部图，所以它有两个色类，每个色类内部没有边，因此边只能位于不同色类的顶点之间。

这里，我们并不知道 \(G\) 是二部图。然而，我们仍然可以考察 \(G\) 的最大的空导出子图，把它的顶点集记作 \(X\)。也就是说，\(X\) 内任意两个顶点之间都没有边，并且不存在拥有多于 \(|X|\) 个顶点、具有这一性质的导出子图。

设 \(Y\) 是 \(G\) 中不在 \(X\) 里的顶点之集。那么 \(|X|+|Y|=n\)。关键在于：\(G\) 中任何顶点的度数都不可能超过 \(|X|\)。事实上，任何顶点的两个邻居之间都不可能相邻，否则就意味着 \(G\) 含有三角形。所以任何顶点的全体邻居构成 \(G\) 的一个空导出子图，因而它们的个数不可能超过 \(|X|\)。

虽然我们不知道 \(G\) 是二部图，但我们确实知道它的边要么位于 \(Y\) 内部，要么连接 \(X\) 与 \(Y\)。这意味着 \(G\) 的所有边至少有一个端点在 \(Y\) 中。所以，如果我们把 \(Y\) 中各顶点的度数相加，就会把 \(G\) 的每条边至少计数一次。因此，\(G\) 的边数 \(E(G)\) 满足 \[E(G)\le\sum_{y\in Y}d_y\le\sum_{y\in Y}|X|=|X|\,|Y|\le\left(\frac{|X|+|Y|}{2}\right)^2=\frac{n^2}{4}.\] 这里第二行之间的不等式来自 (6.1)，即几何平均与算术平均之间的不等式。♦

注意我们在定理 6.6 的证明中也用到了不等式 (6.1)。我们指出，在上面的证明里，在 \(E(G)\le\sum_{y\in Y}d_y\) 这一步，等号成立当且仅当 \(G\) 的所有边都恰好有一个端点在 \(Y\) 中，也就是当 \(G\) 是以 \(X\) 与 \(Y\) 为色类的二部图时。所以，再一次地，提供“不含三角形时边数最多”的图，正是完全二部图。

这条证明的逻辑脉络没有“二部”这个免费条件时，作者人为造出一个：取最大的“互不相连”的顶点组 \(X\)（空导出子图）。无三角形 ⟹ 任一点的邻居互不相连 ⟹ 邻居都落在某个空集里 ⟹ 每点度数 \(\le|X|\)。再把所有边“记账”到 \(Y\) 这一侧，用 \(|X|\,|Y|\) 封顶，最后用算术–几何平均把 \(|X|\,|Y|\) 压到 \(n^2/4\)。
例（具体跟踪一遍记账，\(n=5\)） 设 \(G\) 有 \(5\) 个顶点且无三角形，并设极值图为 \(K_{2,3}\)（红侧 \(2\) 点、蓝侧 \(3\) 点）。它的最大空导出子图就是那 \(3\) 个互不相连的蓝点，记 \(X\)（\(|X|=3\)）；于是 \(Y\) 是其余 \(2\) 个红点（\(|Y|=2\)）。
  1. 每个顶点的度数 \(\le|X|=3\)（因为它的邻居必须互不相连，而互不相连的点最多 \(|X|=3\) 个）。这里红点度数恰为 \(3\)，蓝点度数为 \(2\)。
  2. 每条边至少一端在 \(Y\)，故 \(E(G)\le\sum_{y\in Y}d_y\le 2\times 3=6=|X||Y|\)。
  3. 再用 \(|X||Y|\le\big(\tfrac{|X|+|Y|}{2}\big)^2=\big(\tfrac{5}{2}\big)^2=6.25\)，取整后 \(E(G)\le 6\)。
  4. 而 \(n^2/4=25/4=6.25\)，与上界一致。无三角形时 \(5\) 点最多 \(6\) 条边，由 \(K_{2,3}\) 达到（此时 \(G\) 恰为二部图，记账步骤取等）。♦
X：最大空集（内部无边） Y：其余顶点 边只在 X–Y 之间（灰）或 Y 内部（红）；X 内部没有边
每条边至少有一端落在 \(Y\)，于是把 \(Y\) 中顶点度数相加，能把每条边至少数到一次。

更一般的方向

现在我们知道了：在一个给定的顶点集上，如果一个图不能含有三角形作为子图，它最多能有多少条边。这个问题可以朝几个自然的方向加以推广。也就是说，三角形既是一个完全图，也是一个圈。人们可以问：如果一个 \(n\) 个顶点上的图不能含有 \(k\) 个顶点的完全图 \(K_k\)，它最多能有多少条边。人们也可以问：如果一个 \(n\) 个顶点上的图不能含有 \(k\) 个顶点的圈 \(C_k\)，它最多能有多少条边。后者还能进一步推广为：如果 \(G\) 不能含有长度为 \(k\) 或更短的圈，它最多能有多少条边。

小结本节用同一套方法（算术–几何平均不等式 + 把边“记账”到一侧）解决了两个极值问题：二部图（定理 6.6）和无三角形图（定理 6.7），两者的极值都由完全二部图 \(K_{\lfloor n/2\rfloor,\lceil n/2\rceil}\) 达到，最大边数都是 \(\lfloor n^2/4\rfloor\)。把“三角形”换成“\(K_k\)”或“圈 \(C_k\)”，就通向更广阔的极值图论问题。
即时自测
  1. 判断长度为 \(5\) 的圈 \(C_5\) 是否为二部图，并说明理由（用命题 6.2）。
  2. \(n=7\) 时，二部图最多有多少条边？达到上界的图是哪个完全二部图？
  3. 在定理 6.7 的证明里，为什么“无三角形”能推出“每个顶点的度数不超过 \(|X|\)”？

返回 全书目录