单点度数约束生成树：复杂度与验证边界

研究状态：待校订。 本页分析候选构造的操作量。运行时间上界与算法是否输出全局最优解是两项独立问题。

参数与符号 #

设 $n=|V|$、$m=|E|$，$E_1$ 为与顶点 $1$ 相连的边集，$E_0=E\setminus E_1$，$d_1=|E_1|$。 图按无向连通简单图理解，$n\ge2$；$r$ 是删除顶点 $1$ 后的连通分量数。

基树、指派与候选排序 #

阶段	操作	开销
输入整理	拆分 $E_0,E_1$，保存边 ID 与权值	$O(n+m)$
非入射边排序	按权值排序 $E_0$	$O(m\log m)$
Kruskal 扫描	每条 $E_0$-边执行查找，合并时记录候选键	$O(m)$ 次 DSU 操作、$O(n)$ 次记录
候选分类	区分分量基边、第一组与剩余组	$O(n)$
候选排序	对至多 $d_1$ 条边分组排序	$O(d_1\log d_1)$
固定根边后补全	初始化新 DSU，再扫描已排序 $E_0$	$O(n+m)$ 次 DSU 操作

采用按秩或按大小合并并结合路径压缩时，DSU 操作具有 $O(\alpha(n))$ 的摊还界；合并后的最小根边必须作为独立的分量元数据维护。 算法页的直观伪代码则直接让较小根边对应的代表成为父节点，不能不加说明地把它等同于按秩合并的实现。

在使用上述经过相应调整的 DSU 实现时，操作量上界为

$$O(m\log m+(n+m)\alpha(n))=O(m\log m),\qquad S(n,m)=O(n+m).$$

等式使用了连通图 $m\ge n-1$。该界只描述候选构造的计算步骤，不包含一份尚不存在的正确性证明或性能测试。

离线补全不等于在线换边 #

实际伪代码是“选定 $k$ 条根边，再运行 Kruskal”，没有逐次执行动态树的删边操作。 因此不能声称每个离线键都等于当前树的路径最大值，也不能由一个整数键直接断言任意在线交换都能在 $O(1)$ 时间内完成。 多次选择后键仍然有效的条件，列在证明校核中。

若采用真正的在线方案，每次加入一条根边时，必须在形成的环上删除一条非根边，才能使指定顶点的度数增加。 Link-Cut Tree 可用于动态维护路径信息，但仍须给出正确的交换规则和不变量。 普通静态树链剖分不能在任意 link/cut 后不加维护地继续使用；在线数据结构本身也不证明贪心策略最优。

可用于对照的小规模基线 #

可以枚举 $E_1$ 中大小为 $k$ 的子集，跳过不能连接全部分量的选择；对每个剩余子集强制保留根边，再用已排序的 $E_0$ 做 Kruskal，最后比较完整降序边权向量。 候选子集数为 $\binom{d_1}{k}$，是否可运行取决于该组合数，而不是一个固定的“顶点数不超过 10”门槛。

仅二分最大边权解决的是瓶颈层面的判定。要得到完整词典序最优解，还需继续处理后续坐标，不能直接把两种目标视为同一算法。

上界、下界与未来优化 #

比较排序任意实数需要 $\Omega(m\log m)$ 次比较，但这不等于生成树问题本身需要完全排序。 普通 MST 已有更快的比较模型算法，例如 Chazelle 的确定性 MST 算法。该结果说明“必须排序所以最优”的推理不成立，并不直接给出本受限问题的复杂度结论。

整数桶排序、基数排序或其他 MST 框架能否用于本问题，取决于候选排序、度约束和词典序目标如何同时保持；在证明完成前，不宣称它们自动带来线性时间。