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

无度限制时的等价性

设边权互异。记生成树 $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)$，依此类推。

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

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

图与权值构造

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

latex \begin{tabular}{c|c|c} 边 & 权值 & 说明 \\ \hline (1,A) & 9 & 与 1 相连 \\ (1,B) & 6 & 与 1 相连 \\ (1,C) & 5 & 与 1 相连 \\ (A,B) & 7 & 非 1 边 \\ (B,C) & 2 & 非 1 边 \\ (C,D) & 1 & 非 1 边 \\ \end{tabular}

要求生成树满足$\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$ 的单点度限制下， “总和最小”与“最大边优先词典序最小”不再等价。

小结

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