极值图问题 | Codeboy's Blog

形式陈述

一个极值图问题由允许的对象、禁用条件和待优化参数三部分组成。最经典的无向简单图版本固定非负整数 $n$ 与有限图族 $\mathcal F$ ，并假设每个 $F\in\mathcal F$ 至少含一条边；在所有不含任何 $F\in\mathcal F$ 作为子图的图 $G$ 中最大化边数：

\max\bigl\{e(G): |V(G)|=n,\ F\nsubseteq G\text{ 对每个 }F\in\mathcal F\bigr\}.

这里 $F\nsubseteq G$ 默认排除普通的、未必诱导的副本：嵌入只须把 $F$ 的边送到 $G$ 的边， $F$ 中的非边在像中可以变成边。若题目排除诱导子图、子式或同态像，必须明确改写包含关系，因为可行图类与答案都会改变。

更一般地，可以最大化团数、最小度、谱半径或超边数；也可以固定边数，最小化被迫出现的禁图副本数。一个完整解答通常包含三个层次：给出最优值，构造达到它的图，并刻画全部取等者。仅有上界而没有匹配构造，或仅展示一个稠密构造而没有排除更优者，都还不是完整的极值结论。

直觉

禁图条件是一条局部禁令，极值目标却追问全局还能堆入多少结构。边越多，邻域重叠越强，某些小图终会被迫出现；极值图恰处在“再加一点就越界”的边缘。好的证明往往把局部禁令转成可求和的不等式，再从等号条件反推出整体形状。

这类问题的难点不只在算一个数。两个图可能边数相同，却离典型极值构造很远；一个只差 $o(n^2)$ 条边的近极值图，又可能在删改少量边后显露出稳定的分部结构。因此极值、超饱和与稳定性分别回答“最多多少”“超过后出现多少副本”和“接近最多时长什么样”，三者是同一条结构链上的不同问题。

例子与边界

以禁止三角形为例。把五个顶点分成大小 $2$ 与 $3$ 的两组，连接全部跨组顶点，得到 $6$ 条边且没有三角形。反过来，若 $G$ 无三角形，则每条边 $uv$ 的两个邻域除 $u,v$ 外不能相交，所以 $d(u)+d(v)\le5$ 。对所有边求和得到

\sum_{v}d(v)^2=\sum_{uv\in E(G)}(d(u)+d(v))\le5e(G).

再由 Cauchy–Schwarz 不等式， $(2e(G))^2\le5\sum_vd(v)^2\le25e(G)$ ，故 $e(G)\le6$ 。这个可核算的小例子同时给出构造、上界和紧性；若要刻画全部取等图，还需补充更精细的结构分析，因为上述不等式链在 $K_{2,3}$ 上并非逐步取等。

边极大与边数最大不能混同。五圈 $C_5$ 无三角形，而且任添一条弦都会造出三角形，所以它在包含意义下已经极大；但它只有 $5$ 条边，仍低于上述最优值 $6$ 。同样，“几乎达到最优边数”也不自动意味着与某个极值图同构，只能在附加的稳定性定理下推出少量编辑距离。

诱导版本的边界尤其明显。普通意义下，完全图 $K_n$ 含三点路径 $P_3$ 作为子图；诱导意义下，它没有诱导 $P_3$ ，因为任取三点都会多出第三条边。若没有写出“诱导”，极值图论的标准约定不能擅自替换。

推论与应用

把最优边数记成函数便得到极值数；禁止完全图时，Turán 定理给出精确答案。若禁图是二分图，密度主项不再由色数直接决定，Zarankiewicz 问题及其关联计数成为另一条主线。

极值结论也常作为存在性证明的阈值：只要一个对象超过上界，就必然含有所需配置。算法分析中，这可以把“逐个搜索所有小结构”换成对边数或度数的证书；加法组合与编码理论则把集合交、差集或禁距关系编码成图，再将图的极值界翻译回原问题。翻译是否有效取决于禁用结构是否被精确保持，不能只凭相似图形套用结论。

参考资料

Béla Bollobás, Extremal Graph Theory, Academic Press, 1978, Chapters I–III.
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, Cambridge University Press, 2023, Chapter 1.
Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, Chapter 7.