单点度数约束生成树：证明校核与反例

研究状态：证明未完成。 原稿的全局最优性结论依赖数个不成立的交换步骤，不能继续作为已证定理引用。本页给出可保留的局部结论、具体反例，以及候选算法仍需补齐的证明。图均按无向连通简单图、 $n\ge2$ 、互异边权理解。

词典序与无约束单次交换 #

将边权按非增序写为 $a_1(T)>\cdots>a_{n-1}(T)$ ，逐项从左向右比较。若 $e\notin T$ ，加入 $e$ 产生唯一环，删除该环上的旧边 $f$ 仍是生成树。当 $w(e)<w(f)$ 时，边权多重集中只把一个较大的数替换成较小的数，排序后的向量严格改善。

这个结论只保证“仍是树且词典序改善”。是否保持指定顶点的度数，必须另行检查。

任意割交换不能保持度约束 #

原稿声称任意割的最小边都能替换指定的跨割树边，并保持度约束。该论证不成立：新边形成的基本环未必包含指定树边，替换的两条边也未必同为根边。

取三角形

w(2,3)=1,\quad w(1,2)=2,\quad w(1,3)=3,\quad k=2.

唯一可行树是 $\{12,13\}$ 。割 $\{2\}$ 的最小跨割边是 $23$ ，却不在这棵最优可行树中。加入 $23$ 后，无论删除旧根边 $12$ 还是 $13$ ，顶点 $1$ 的度都降为 $1$ 。因此普通 MST 的割性质不能原样搬到这个受限可行域。

可行性与最低度数基树 #

删除顶点 $1$ 后，分量为 $C_1,\ldots,C_r$ 。每个分量都必须有至少一条根边，且任何可行树满足

r\le k\le d_1=\deg_G(1).

反之，若每个分量都存在根边且上式成立，先每分量选一条，再增加不同邻点对应的根边至 $k$ 条。这些根边是星形无环集合。将它们收缩后，每个分量的内部边仍能连接该分量的其他顶点，所以可以扩充为生成树；条件在声明图类下充分。

当 $k=r$ 时，每个分量只能使用一条根边，且分量内部必须是一棵生成树。各分量的最小根边和内部 MST 可独立选择，合并后得到该等式度数条件下的词典序最优基树。

原稿把此结论扩展到所有 $\deg_T(1)\ge r$ 的树，范围过大。反例是 $w(12)=1,w(13)=2,w(23)=10$ ： $r=1$ 的基树边权为 $(10,1)$ ，度数为 $2$ 的树却有更小向量 $(2,1)$ 。这个反例也说明，不能要求所有更高度数的最优树保留基树的全部非根边。

增度必须删除非根边 #

在前述权值 $(w(23),w(12),w(13))=(1,2,3)$ 的三角形中，基树为 $\{12,23\}$ 。加入 $13$ 后，原路径最大边是根边 $12$ 。删掉它只会把一条根边换成另一条，度数仍为 $1$ ；要得到度数 $2$ ，必须删除非根边 $23$ 。

因此应在 $P_T(1,x)\cap E_0$ 内选择删除边，而不是使用整条路径的最大值。对固定待加边，删除最大非根边是最佳的单次增度交换。这不能自动证明所有候选之间的选择顺序。

最大排序键相同仍需比较候选 #

取基树 $T=\{12,23,34\}$ ，权值为

w(12)=2,\quad w(23)=10,\quad w(34)=1, \quad w(13)=4,\quad w(14)=5.

候选 $13$ 、 $14$ 的路径都包含最大非根边 $23$ 。删 $23$ 后，两个结果分别为 $(4,2,1)$ 与 $(5,2,1)$ 。仅按路径最大权 $10$ 排序无法区分它们；原稿声称任意这样的最大键候选都单步最优，遗漏了平局。即使给出确定的次关键字，仍需证明该规则对后续全局选择有效。

删除树边不是降度生成树 #

原前缀最优性归纳从任意可行树 $S$ 删除一条根边后，将所得 $S'$ 直接视为较低度数的生成树。但删除树的任意一条边会产生两个连通分量，所以归纳假设不能应用到这个森林。

要修复证明，需要构造一次“删除根边、加入非根边”的交换，证明连通性、恰好降度以及所需的词典序比较都成立。局部选择最优也不自动推出不同前缀之间可以不劣地交换；这一点不能用“形式化地调整”省略。因此原来的前缀最优性定理及由它推导的全局正确性定理尚未成立。

离线键不等于任意时刻的路径瓶颈 #

仍取上面的四点图。Kruskal 先合并 $34$ ，把权值 $1$ 指派给较大的根边候选 $14$ ；随后合并 $23$ ，把权值 $10$ 指派给候选 $13$ 。于是 mx[4]=1，但初始基树中从 $1$ 到 $4$ 的最大非根边权为 $10$ 。

这直接否定“离线键始终等于当前路径最大值”的字面断言。它不单独证明最终离线算法错误：选择 $13$ 后，其他候选的有效路径确实会变化。要证明最终算法，仍需一个描述选择次序与路径变化的归纳不变量，而非把静态键和任意时刻的动态值直接等同。

固定根边后的补全 #

固定一个覆盖全部分量、含 $k$ 条根边的集合 $A$ 后，先把 $A$ 收缩，再对 $E_0$ 运行 Kruskal，得到该固定集合下的最优补全。这一步不能说明 $A$ 本身的选择已经最优；对所有合法根边子集进行枚举，是小图可采用的独立对照方法。

互异边权保证不同树具有不同的排序向量，所以有限非空可行域中最优树唯一。这是最优解本身的唯一性，不能用它反推某个未证算法一定找到了该树。

尚待完成 #

根边候选顺序对所有可行根边集合的支配关系。
离线指派在候选逐步加入后的精确不变量。
共享排序键的处理及其与全局最优性的关系。
保持生成树和度数的前缀交换引理。
可复核实现、与枚举基线的边界测试，以及独立性能实验。

在这些工作完成前，本专题不宣称已经证明一般 $k>r$ 情况的全局最优性。