U 群提问：怎么证最大割下界 m/2 + [n/4]

· · 算法·理论

::::info[注意]{open} 本文是测试使用大模型辅助写作博客文章的效果的实验性文本。 ::::

在 UOJ 群中，有同学问起：对于一个 n 个顶点、m 条边的简单连通图，为什么它的最大割至少是 \frac{m}{2} + \bigl\lfloor \frac{n}{4} \bigr\rfloor？这个下界常被称为 Edwards–Erdős 界，由 Erdős 猜想，Edwards (1973) [1] 首先证明。本文将给出一个基于 DFS 树与概率方法的严格带权证明，并由此导出经典的无权下界，同时展示能取到该下界的紧图构造。该带权证明思路源自 Gutin 与 Yeo (2023) [2]（预印本可在 https://arxiv.org/abs/2104.05536 阅读），我对其进行了整理与简化在群里回答了问题，并经 DeepSeek V4 Pro 模型辅助润色成文。

1. 证明准备与目标

设 G = (V, E) 为连通简单图，\lvert V \rvert = n，\lvert E \rvert = m。对每条边 e \in E 赋予非负权重 w(e) \ge 0，并记 w(S) = \sum_{e \in S} w(e) 对边子集 S \subseteq E。图的最大割权值 \operatorname{Max-Cut}(G, w) 是所有顶点划分中跨割边的权重之和的最大值。当所有权重 w(e) = 1 时，\operatorname{Max-Cut}(G, w) 即通常的最大割边数 \operatorname{Max-Cut}(G)。

我们首先证明一个较一般的不等式：对任意非负权 w 及 G 的任意一棵 DFS 树 T，用 w(T) 简记 T 的边集权值和，有

\operatorname{Max-Cut}(G, w) \ge \frac{w(E)}{2} + \frac{w(T)}{4} \text{。} \tag{1}

然后取 w \equiv 1，则 w(E) = m，而任何 DFS 树的边数恰为 n - 1，故 w(T) = n - 1，从而

\operatorname{Max-Cut}(G) \ge \frac{m}{2} + \frac{n - 1}{4} \text{。} \tag{2}

再利用最大割边数为整数并取上整，便得到最终的目标下界

\operatorname{Max-Cut}(G) \ge \biggl\lceil \frac{m}{2} + \frac{n - 1}{4} \biggr\rceil \ge \frac{m}{2} + \biggl\lfloor \frac{n}{4} \biggr\rfloor \text{。} \tag{3}

接下来我们专注于证明核心不等式 (1)。

2. DFS 树与随机染色——下界的证明

2.1 DFS 树与边分类

任取 G 的一棵 DFS 树 T，规定根结点深度为 0。对每条树边 u v（u 是父亲，v 是儿子），定义其深度为 u 的深度。按深度的奇偶性将这些树边分为两类：

E_{\text{even}} = \{ e \in E(T) \mid \text{深度为偶数} \} \text{，} \qquad E_{\text{odd}} = \{ e \in E(T) \mid \text{深度为奇数} \} \text{。}

两类边不交，且并集为 T。设其中权值和较大的一类为 X，则

w(X) \ge \frac{w(T)}{2} \text{。}

无向图 DFS 树的关键性质是：所有非树边均为祖孙边，没有横叉边，因此每条非树边连接的两个顶点深度之差至少为 2。

2.2 随机染色方案

利用 X 将树的各层组织成若干染色块：

现在按以下规则独立地随机染色（全图顶点最初未染色）：

  1. 单层块：独立地以 \frac{1}{2} 概率将该层所有顶点染为黑色，否则全部染为白色。
  2. 双层块 (i, i + 1)：独立地以 \frac{1}{2} 概率将第 i 层染黑、第 i + 1 层染白；以 \frac{1}{2} 概率将第 i 层染白、第 i + 1 层染黑。

由独立性立刻得到：不同染色块之间的顶点颜色相互独立；同一单层块内顶点同色；同一双层块内相邻两层的顶点强制异色；且对任意顶点，其最终为黑色的边的概率均为 \frac{1}{2}。

2.3 期望权重与下界

考察任意一条边被割（两端异色）的概率：

因此，在该随机染色下，割边总权重的期望为

\begin{aligned} \mathbb{E}[\text{割权}] &= 1 \cdot w(X) + \frac{1}{2} \bigl( w(T) - w(X) \bigr) + \frac{1}{2} \bigl( w(E) - w(T) \bigr) \\ &= \frac{w(E)}{2} + \frac{w(X)}{2} \ge \frac{w(E)}{2} + \frac{w(T)}{4} \text{。} \end{aligned}

期望值达到该数，故必存在某种染色使得实际割边总权重不小于期望值，因此

\operatorname{Max-Cut}(G, w) \ge \frac{w(E)}{2} + \frac{w(T)}{4} \text{。}

这便证明了 (1) 式。

现在取所有边权 w(e) = 1，则 w(E) = m，而 DFS 树 T 恰有 n - 1 条边，故 w(T) = n - 1。代入 (1) 立即得到

\operatorname{Max-Cut}(G) \ge \frac{m}{2} + \frac{n - 1}{4} \text{。} \tag{2}

为得到最终形式 \frac{m}{2} + \bigl\lfloor \frac{n}{4} \bigr\rfloor，注意到最大割边数为整数，故有

\operatorname{Max-Cut}(G) \ge \biggl\lceil \frac{m}{2} + \frac{n - 1}{4} \biggr\rceil \text{。}

又易证 \bigl\lceil \frac{m}{2} + \frac{n - 1}{4} \bigr\rceil \ge \frac{m}{2} + \bigl\lfloor \frac{n}{4} \bigr\rfloor。令 n = 4 k + r（r = 0, 1, 2, 3），则 \frac{n - 1}{4} = k + \frac{r - 1}{4}，\lfloor n / 4 \rfloor = k。于是

\biggl\lceil \frac{m}{2} + \frac{n - 1}{4} \biggr\rceil = k + \biggl\lceil \frac{m}{2} + \frac{r - 1}{4} \biggr\rceil \text{。}

对 r = 0, 1, 2, 3 逐一验证均可知 \bigl\lceil \frac{m}{2} + \frac{r - 1}{4} \bigr\rceil \ge \frac{m}{2}（例如 r = 0 时 \bigl\lceil \frac{m}{2} - \frac{1}{4} \bigr\rceil \ge \frac{m}{2} 恒成立）；故

k + \biggl\lceil \frac{m}{2} + \frac{r - 1}{4} \biggr\rceil \ge \frac{m}{2} + k = \frac{m}{2} + \biggl\lfloor \frac{n}{4} \biggr\rfloor \text{。}

这就完成了整个下界的严格证明。

3. 紧图构造——何时能取到下界？

上述下界在取整意义下是紧的，即存在无穷多连通图使得

\operatorname{Max-Cut}(G) = \biggl\lceil \frac{m}{2} + \frac{n - 1}{4} \biggr\rceil \text{。}

下面给出几类覆盖从稀疏到稠密广泛参数范围的构造。

3.1 完全图 K_n（最稠密情形）

$$ L = \frac{m}{2} + \frac{n - 1}{4} = \frac{n (n - 1)}{4} + \frac{n - 1}{4} = \frac{n^2 - 1}{4} \text{。} $$ - 当 $n = 2 k$ 时，$L = k^2 - \frac{1}{4}$，$\lceil L \rceil = k^2$； - 当 $n = 2 k + 1$ 时，$L = k^2 + k$（整数），$\lceil L \rceil = k^2 + k$。 而在两种情形下 $\lfloor n^2 / 4 \rfloor$ 亦分别等于 $k^2$ 与 $k^2 + k$，故 $\operatorname{Max-Cut}(K_n) = \lceil L \rceil$ 恒成立。完全图是最稠密的一类紧图（$m \sim n^2 / 2$）。 ### 3.2 风车图（奇完全图共享一点） 取 $k$ 个奇完全图 $K_{2 t + 1}$（$t \ge 1$），将它们的一个公共顶点粘合在一起，常称为风车图，记作 $W(k, t)$。 - 顶点数：$n = 2 k t + 1$； - 边数：$m = k \binom{2 t + 1}{2} = k t (2 t + 1)$； - 最大割：将公共点染黑；在每个花瓣 $K_{2 t + 1}$ 中，将剩余 $2 t$ 个点分为 $t$ 个黑点与 $t$ 个白点，则花瓣内部割边数达到其最大割 $t (t + 1)$（花瓣之间除公共点外无边）。总最大割为 $$ \operatorname{Max-Cut}(W(k, t)) = k \cdot t (t + 1) \text{。} $$ 计算 $L$： $$ \begin{aligned} L = \frac{m}{2} + \frac{n - 1}{4} &= \frac{k t (2 t + 1)}{2} + \frac{2 k t}{4} \\ &= k t \biggl( t + \frac{1}{2} \biggr) + \frac{k t}{2} = k t (t + 1) \text{。} \end{aligned} $$ $L$ 为整数且恰好等于最大割。风车图**无需取整即达下界**。 调节 $t$ 可改变平均度（$\approx 2 t + 1$），调节 $k$ 可放大规模。例如 $t = 1$ 时是 $k$ 个三角形共享一点（$n = 2 k + 1, \; m = 3 k$），平均度约 $3$；$t = 2$ 时是 $k$ 个 $K_5$ 共享一点（$n = 4 k + 1, \; m = 10 k$），平均度约 $5$。 ### 3.3 奇完全图的树形粘合 将若干个奇完全图 $K_{o_1}, K_{o_2}, \ldots, K_{o_s}$（每个 $o_i \ge 3$ 为奇数）按照一棵树的结构在公共点上粘合（所得图的块图是一棵树），得到图 $G$。此时 - $n = 1 + \sum (o_i - 1)$， - $m = \sum \binom{o_i}{2}$， - 最大割 $= \sum \frac{o_i^2 - 1}{4}$（各部分最大割之和）。 代入得 $$ L = \frac{m}{2} + \frac{n - 1}{4} = \sum \biggl( \frac{o_i(o_i - 1)}{4} + \frac{o_i - 1}{4} \biggr) = \sum \frac{o_i^2 - 1}{4} \text{，} $$ 依然是整数且等于最大割。通过选取不同大小与个数的奇团，可非常灵活地调节 $n$ 与 $m$，构造大量取到下界的图。 ### 3.4 共享边的构造与偶数顶点例子 若希望 $n$ 为偶数，可让两个奇完全图沿一条边粘合。设两团为 $K_{2 a + 1}$ 与 $K_{2 b + 1}$（$a, b \ge 1$），共享边 $u v$，所得图记作 $G(a, b)$。 - $n = (2 a + 1) + (2 b + 1) - 2 = 2 a + 2 b$； - $m = \binom{2 a + 1}{2} + \binom{2 b + 1}{2} - 1$； - 最大割：令 $u$ 黑、$v$ 白；在团 $A$ 内安排 $a + 1$ 个黑点（含 $u$）与 $a$ 个白点（含 $v$），在团 $B$ 内同样作最优划分。则两团内部均达到其最大割 $a (a + 1)$ 与 $b (b + 1)$。总最大割为 $$ \operatorname{Max-Cut}(G(a, b)) = a (a + 1) + b (b + 1) \text{。} $$ 计算 $L$： $$ \begin{aligned} L &= \frac{m}{2} + \frac{n - 1}{4} \\ &= \frac{a (2 a + 1) + b (2 b + 1) - 1}{2} + \frac{2 a + 2 b - 1}{4} \\ &= a (a + 1) + b (b + 1) - \frac{3}{4} \text{。} \end{aligned} $$ $\lceil L \rceil = a (a + 1) + b (b + 1)$，恰等于最大割。例子：两个 $K_3$ 共享一边得「钻石图」（$n = 4, m = 5$，最大割 $4$）；两个 $K_5$ 共享一边得 $n = 8, m = 19$，最大割 $12$。 通过多次进行这类“团和”操作，可生成更多偶数顶点的紧图。 ### 3.5 小结 - 对**任意** $n \ge 2$，完全图已使下界成为精确界。 - 在稀疏方向，风车图、奇团树形粘合、$C_5$（$n = 5, m = 5$，最大割 $4$）等均能达到下界。 - 无法达到下界的典型是二分图（特别是树），其最大割等于 $m$，而下界约 $0.5 m + 0.25 n$，对 $n \ge 5$ 的树远小于 $m$。但除此之外，几乎对所有密度都存在取到下界的连通图。 上述构造展示了该下界在极宽泛范围内的紧性，其中完全图即是最早由 Edwards 给出的紧例。 ## 4. 结语 利用 DFS 树“无横叉边”的优雅性质，配合按深度奇偶分层的随机染色，我们仅通过几行期望计算就得到了最大割的经典下界，充分展示了概率方法在图论中的威力。随后构造的几族紧图则表明，该下界在极端宽泛的参数范围内都是不可改进的。 ### 参考文献 1. C. S. Edwards. *Some Extremal Properties of Bipartite Subgraphs*. Can. J. Math., 25(3):475–485, 1973. DOI: <https://doi.org/10.4153/CJM-1973-048-x>。 2. Gregory Gutin and Anders Yeo. *Lower Bounds for Maximum Weighted Cut*. SIAM J. Discret. Math., 37(2):1142–1161, 2023. DOI: <https://doi.org/10.1137/21M1411913>。预印本可在 <https://arxiv.org/abs/2104.05536> 获取。