单点度数约束生成树：阶段结论与后续问题

当前可以确认的结论 #

本专题研究一个指定顶点的度数恰好等于 $k$ 时，生成树边权按从大到小比较的词典序目标。 无度约束下的普通 MST 结论提供基础工具，但有约束时必须额外检查交换是否保持度数。

• 删除指定顶点后的每个连通分量必须至少有一条根边；在无向连通简单图中，可行度数范围为 $r\le k\le d_1$。
• 当 $k=r$ 时，各分量内部 MST 与各自最小根边构成该度数下的最优基树。
• 固定一个合法根边集合后，Kruskal 可以给出对应的最优补全。
• 研究稿保留了一个离线候选顺序及完整伪代码，见候选算法。

尚不能作为结论的部分 #

证明校核已经指出：一般割交换不保持度约束、删除路径最大边不一定增度、删除树边得到的是森林，以及静态键不等于任意时刻的动态路径瓶颈。 因此“算法已严格证明全局最优”“离线指派只影响效率、不影响正确性”的结论仍待完成。

排序主导的 $O(m\log m)$ 是一种候选实现的操作量上界，不是已证明的受限问题理论下界。 也不能仅更换排序或普通 MST 子程序，就宣称整个受限算法达到线性时间。

实验证据 #

本专题尚未附有可复核的实现、输入数据、随机种子、基线、运行环境和结果报告。 因此不再保留“在真实网络上验证优越性”“已支持 $10^5$ 条边”等未经材料支持的成果表述。 小图反例核验只用于校核数学论证，不是一般正确性或性能证据。

后续顺序 #

1. 先修复交换证明，确定候选顺序是否成立；证明失败时据反例调整算法。
2. 明确简单图、互异边权、目标度数和无解输入的完整契约。
3. 写出可运行实现，与根边子集枚举基线做小规模系统对照。
4. 记录数据、随机种子、硬件与耗时，区分正确性实验和性能实验。
5. 在单点静态问题稳定后，再讨论重权、并行边、多点约束或动态场景。

当前成果是清晰的问题定义、可验证的局部构造和可继续检查的算法草稿，而不是已完成的一般最优算法。