图论中的极值问题 极值图论是图论的一个重要分支，主要研究在特定约束条件下图参数的极值（最大值或最小值）以及达到极值的图结构。例如：在具有n个顶点的图中，若不允许出现三角形，则边数的最大值是多少？达到该最大值的图有哪些特征？这类问题通常涉及图参数（如边数、顶点度、团数等）与图性质（如连通性、禁止子图）之间的权衡。 1. 基本概念与问题形式 极值图论的核心问题是： 给定图性质\(\mathcal{P}\)（如“不含三角形”），设\(\mathcal{G}_ n\)为所有n顶点且满足\(\mathcal{P}\)的图的集合。 定义极值函数\(ex(n, \mathcal{P})\)为\(\mathcal{G}_ n\)中图的最大边数。 进一步研究极值图（达到\(ex(n, \mathcal{P})\)的图）的结构特征。 示例 ： 若\(\mathcal{P}\)为“不含三角形”，则Turán定理指出： \(ex(n, K_ 3) = \lfloor \frac{n^2}{4} \rfloor\)， 极值图为完全二部图\(K_ {\lfloor n/2 \rfloor, \lceil n/2 \rceil}\)。 2. 经典工具：Turán定理与推广 Turán定理是极值图论的基石，解决的是禁止完全图\(K_ r\)时的最大边数问题： 定理 ：若n顶点图不含\(K_ {r+1}\)，则边数不超过\(\left(1 - \frac{1}{r}\right) \frac{n^2}{2}\)， 极值图是Turán图\(T(n, r)\)，即顶点被划分为r个尽可能均匀的集合，每部分内部无边，不同部分之间连边。 推广 ： Erdős–Stone定理将禁止子图推广到一般图\(H\)，指出\(ex(n, H) = \left(1 - \frac{1}{\chi(H)-1} + o(1)\right) \binom{n}{2}\)，其中\(\chi(H)\)为H的色数。该定理表明，极值问题的主要难度集中在\(\chi(H)=2\)（二部图）的情形。 3. 二部图情形的精细分析 当禁止子图H是二部图时，Erdős–Stone定理仅给出平凡上界\(o(n^2)\)，需更精细的工具： Kővári–Sós–Turán定理 ：禁止完全二部图\(K_ {s,t}\)时，有\(ex(n, K_ {s,t}) \leq O(n^{2 - 1/s})\)。 匹配极值 ：禁止k条互不相邻的边（匹配\(M_ k\)）时，极值图是几乎完全的图（仅删除少数边）。 此类问题常使用 概率方法 或 正则引理 证明上界，并构造代数图（如极有限域上的点线关联图）达到下界。 4. 其他极值问题变体 超图极值问题 ：禁止超图子结构时，极值函数的行为可能更复杂（例如Turán密度尚未完全确定）。 局部约束 ：限制最大度、最小度等参数时的极值问题（如Dirac定理：最小度≥n/2的图必含哈密顿圈）。 图兰类问题 ：研究在禁止子图条件下，其他参数（如色数、直径）的极值。 5. 现代方法与开放问题 稳健极值性 ：若图接近极值边数，则其结构是否必然接近极值图？ 随机图下的极值问题 ：在随机图中以高概率满足性质时，极值函数的阈值行为。 组合优化交叉 ：极值图论与算法设计（如近似算法禁用结构分析）密切相关。 极值图论通过“极值”这一视角，揭示了图结构的深层约束与平衡，是连接组合数学、概率论和理论计算机科学的重要桥梁。