词典序与普通最小生成树在单点度限制下的区别

无度限制时的等价性 #

设边权互异。记生成树 $T$ 的边权从小到大排序为

$$\mathbf{w}(T)=(w_{[1]}(T)\le \cdots \le w_{[n-1]}(T)).$$

我们采用“最大边优先”的词典序：比较两棵树 $T,T'$ 时，先比较 $\max(T)=w_{[n-1]}(T)$；若相等，再比较 $w_{[n-2]}(\cdot)$，依此类推。

命题 无度约束时的等价性

在无额外约束（尤其无度限制）且边权互异的情况下，Kruskal 算法得到的最小生成树 既是总权值最小的生成树，也是最大边优先的词典序最小生成树；因而两种目标等价，且最优解唯一。

证明要点

Kruskal 按升序依次选边，满足切分性质与环性质，得到唯一 MST。另一方面，Kruskal 的过程首先确保最大边最小（即为 MBST），若存在另一树在某个从后往前的坐标更小，则与切分/环性质矛盾。由此该 MST 同时也是按“最大边优先”的词典序最小解。

单点度限制下的不等价性：一个反例 #

当加入“$\deg_T(1)=k$”的单点度数恰好等于 $k$ 约束时，可行域改变，导致“总和最小”与“词典序最小（最大边优先）”不再等价。下面给出一个极小反例，展示两种目标将选择不同的可行树。

图与权值构造 #

考虑顶点集合 $V=\{1,A,B,C,D\}$，边与权值如下（边权互不相同）：

边	权值	说明
$(1,A)$	9	与顶点 1 相连
$(1,B)$	6	与顶点 1 相连
$(1,C)$	5	与顶点 1 相连
$(A,B)$	7	不与顶点 1 相连
$(B,C)$	2	不与顶点 1 相连
$(C,D)$	1	不与顶点 1 相连

要求生成树满足$\deg_T(1)=2$。

可行性直观 #

非 $1$ 边 $(A,B),(B,C),(C,D)$ 把 $\{A,B,C,D\}$ 串联起来。 由于度数必须恰为 2，最终树中将选恰好两条与 1 相连的边，并在由这两条 $1$-边形成的若干环上删除一条非 $1$ 边以保持生成树结构（否则度数会被破坏）。

两种目标在该图上的最优解 #

总权值最小（在可行域内） #

选择 $(1,A):9$ 与 $(1,C):5$ 两条 $1$-边。此时 $A$ 与 $C$ 在 $\{A,B,C\}$ 中的唯一路径为 $A\!-\!B\!-\!C$（边权 $7,2$），形成的环包含 $(A,B)$ 与 $(B,C)$。 为使总权值尽量小且保持 $\deg_T(1)=2$，删除环上的一条非 $1$ 边且应删更重者 $(A,B):7$。 再保留 $(B,C):2$ 与 $(C,D):1$ 以保证连通。 得到生成树

$$T_{\mathrm{sum}}=\{(1,A):9,\ (1,C):5,\ (B,C):2,\ (C,D):1\},$$

总权值为 $9+5+2+1=17$，其边权升序为 $(1,2,5,9)$，最大边为 $9$。

词典序最小（最大边优先） #

为尽可能减小最大边，选择 $(1,B):6$ 与 $(1,C):5$ 两条 $1$-边。 此时 $B$ 与 $C$ 的路径为 $(B,C):2$；为保持 $\deg_T(1)=2$，在形成的环上必须删除该非 $1$ 边 $(B,C):2$， 并保留 $(A,B):7$ 与 $(C,D):1$ 以保证连通。 得到生成树

$$T_{\mathrm{lex}}=\{(1,B):6,\ (1,C):5,\ (A,B):7,\ (C,D):1\},$$

总权值为 $6+5+7+1=19$，其边权升序为 $(1,5,6,7)$，最大边为 $7$。

比较与结论 #

• 最大边比较：$\max(T_{\mathrm{lex}})=7 < 9=\max(T_{\mathrm{sum}})$，因此 $T_{\mathrm{lex}}$ 在“最大边优先”的词典序下更优；
• 总权值比较：$\sum T_{\mathrm{sum}}=17 < 19=\sum T_{\mathrm{lex}}$，因此 $T_{\mathrm{sum}}$ 在“总和最小”意义下更优；
• 两者最优解不同，说明在$\deg_T(1)=2$ 的单点度限制下， “总和最小”与“最大边优先词典序最小”不再等价。

注 为何需要谨慎“删边”

度约束为“恰等于 $k$”。一旦选定 $k$ 条与 1 相连的边，后续在环上删边时必须避免删掉这 $k$ 条 $1$ 边；否则度数会下降、违反约束。由此，两种目标在“删哪条环边”上有不同偏好：词典序目标优先删掉当前路径上的最大边，加权和目标则倾向删掉最重的那条边（即使会让最大边升高）。

小结 #

• 在无度限制时，两种目标等价且可由 Kruskal 同时实现；
• 在单点度限制（$\deg_T(1)=k$）时，两种目标可能分叉：词典序解优先压低最大边，而总和解优先压低总权值；
• 上述反例用最小规模清晰地展示了分歧：$T_{\mathrm{lex}}$ 的最大边更小但总和更大，$T_{\mathrm{sum}}$ 则相反。