nan2inf .cn
数学 旧 .com 迁移

图论与组合：讨论班 / 区别比较

从旧 .com 全量搬运的历史内容，来源路径：/math/课程/图论与组合/chapters/讨论班/区别比较/

约 2 分钟阅读
migrationlegacy-commathcourse-notecourse

迁移来源

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

无度限制时的等价性 #

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

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

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

tip

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

note

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

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

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

图与权值构造 #

考虑顶点集合 V={1,A,B,C,D}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\deg_T(1)=2。

可行性直观 #

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

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

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

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

Tsum={(1,A):9, (1,C):5, (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=179+5+2+1=17，其边权升序为 (1,2,5,9)(1,2,5,9)，最大边为 99。

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

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

Tlex={(1,B):6, (1,C):5, (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=196+5+7+1=19，其边权升序为 (1,5,6,7)(1,5,6,7)，最大边为 77。

比较与结论 #

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

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

小结 #

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

讨论

评论

正在加载评论...