单点度数约束生成树：候选算法与完整伪代码

研究状态：待校订。 本页的离线流程是一种候选构造，尚不能作为已证明的词典序最优算法使用。以下保留完整步骤，并将已验证的可行性与仍待证明的选边顺序分开。原来的“删路径最大边就能增度”叙述有反例，见证明校核。

目标与输入范围 #

设 $G=(V,E)$ 是无向连通简单图， $n\ge2$ ，顶点编号为 $1,\ldots,n$ ，边权互异。要求 $\deg_T(1)=k$ ，并最小化从大到小排列的完整边权向量。等价地，若写为升序向量

\mathbf w(T)=(w_{[1]}\le\cdots\le w_{[n-1]}),

则先比较 $w_{[n-1]}$ ，再比较 $w_{[n-2]}$ ，依此类推。并行边、自环、重权以及 $n=1$ 的情形不在这份伪代码的输入范围内。

基树的构造 #

记 $E_1$ 为所有与顶点 $1$ 相连的边， $E_0=E\setminus E_1$ 。在 $V\setminus\{1\}$ 上对 $E_0$ 按权升序运行 Kruskal，得到最小生成森林 $F_0^{\min}$ ，连通分量为 $C_1,\ldots,C_r$ 。对每个分量取

b_{\min}(C_i)\in\arg\min\{w(1,v):v\in C_i,\ (1,v)\in E\}.

若某个分量没有根边，输入不可行；否则 $T_r^{\min}=F_0^{\min}\cup\{b_{\min}(C_i):1\le i\le r\}$ 是度数为 $r$ 的生成树。当 $k=r$ 时，各分量内部的生成树和唯一根边可独立最小化，基树是该度数条件下的最优解。这不意味着任意更高度数的最优树都必须包含整棵基树。

在线交换的必要限制 #

向当前树 $T$ 加入未选根边 $e=(1,x)$ 会形成唯一环。要让度数增加 $1$ ，必须删除路径 $P_T(1,x)$ 上的一条非根边。可比较的单步瓶颈应定义为

M_T^0(1,x)=\max\{w(f):f\in P_T(1,x)\cap E_0\},

而不是整条路径上包括旧根边在内的最大值。简单图中的未选根边对应路径至少含一条非根边。对某个固定候选 $e$ ，删掉这样的最大非根边是该次交换的最佳选择：当 $w(e)<M_T^0$ 时改进， $w(e)>M_T^0$ 时劣化。这些是单次交换的结论，不构成不同候选之间的全局贪心证明。

离线指派与候选顺序 #

研究稿尝试在 Kruskal 合并分量时保存其最小根边：若两个分量的最小根边权为 $a\le b$ ，就把当前合并边的权值记到较大者对应候选的 mx 上。直观上，这是为以后拆分该连接记录一个可能的替换代价。

随后按三段组织候选：

每个最终连通分量的一条最小根边。
满足 val[v] < mx[v] 的候选，按 mx 降序排列。
其余有限根边，按自身权值升序排列。

最后取前 $k$ 条根边，再在新的 DSU 上用 $E_0$ 补成树。不同候选可能共享同一个 mx。下面用自身权值、边 ID 补上确定的平局顺序，便于复现；这个约定本身不证明最优性。离线 mx 也不能无条件解释成当前树的 $M_T^0$ ，两者的等价性仍待证明。

完整伪代码 #

下列 val、id、mx、tr 与两个 Kruskal 扫描分别对应读边、指派、分类、选边和补全阶段。 infeasible 表示题目无可行解；invalid-input 表示输入超出声明范围；internal-check-failed 则应当视为实现错误。代码是算法记法，不是可直接运行的 C/C++。

输入：连通无向简单图 G=(V,E)，互异有限边权 w，指定顶点 1，整数 k
输出：满足 deg_T(1)=k 的候选生成树 T（全局最优性待证明）

检查 n>=2、顶点编号、连通性、无自环/平行边、互异有限权值
若检查失败，返回 invalid-input
对 v=2..n：val[v] = +infinity，id[v] = none
E0 = []
for e=(x,y,w_e,id_e) in E:
    if x==1 or y==1:
        v = 不等于 1 的另一端
        if w_e < val[v]:
            val[v] = w_e
            id[v] = id_e
    else:
        E0.append(e)
d1 = 有限 val[v] 的数量
if k<0 or k>d1: return infeasible

按 (权值, ID) 升序排序 E0
初始化 DSU：fa[v]=v；find 使用路径压缩
对 v=2..n：mx[v] = -infinity
for e=(u,v,w_e,id_e) in E0:
    x=find(u); y=find(v)
    if x==y: continue
    if val[x] > val[y]: swap(x,y)
    fa[y]=x
    mx[y]=w_e
    # x 的 val 对应合并后分量的最小根边
    # y 的 mx 保存较大候选被指派的合并边权

roots = [v in 2..n where find(v)==v]
r = len(roots)
if 任一 roots 中的 v 满足 id[v]==none: return infeasible
if k<r: return infeasible

tr=[]
for v in roots:
    tr.append(原边 id[v])
    val[v]=+infinity
p=len(tr)

first=[]
for v in 2..n:
    if val[v] < mx[v]:
        first.append((原边 id[v], mx[v]))
        val[v]=+infinity
按 (-mx, 边权, ID) 排序 first
把 first 的原边依次追加到 tr
p=len(tr)

rest=[]
for v in 2..n:
    if val[v] < +infinity:
        rest.append(原边 id[v])
按 (边权, ID) 排序 rest
依次追加 rest 到 tr
if len(tr)<k: return internal-check-failed

重新初始化 DSU：fa[v]=v
T=[]
for e in tr[0:k]:
    if find(e.x)==find(e.y): return internal-check-failed
    合并 e.x、e.y 的分量
    T.append(e)
for e in E0:
    x=find(e.x); y=find(e.y)
    if x!=y:
        合并 x、y 的分量
        T.append(e)
if len(T)!=n-1 or deg_T(1)!=k: return internal-check-failed
return T

读边时只有更新最小权值才同步更新 ID，避免权值与原边不一致。本页虽限定简单图，仍保留这个必要的数据一致性检查。若要采用按秩合并获得标准 DSU 摊还界，需把“分量代表”与“最小根边的候选身份”分开存储，不能仅替换 fa[y]=x 而遗漏元数据更新。

已知结论与待证事项 #

可行性条件是每个 $C_i$ 都有根边，且 $r\le k\le d_1$ 。初始根边覆盖所有分量；在简单图中额外根边组成星形无环集合，之后可以用 $E_0$ 补成生成树。
固定前 $k$ 条根边后，Kruskal 给出该固定选择下的最优补全。
未完成的关键是：为什么三段候选顺序选出的根边集合，优于所有其他合法的 $k$ 条根边集合。
还需验证离线键在多次选择后的含义、共享键的平局规则、与在线交换的关系，以及实现的复杂度和边界测试。

因此，当前输出应称为“可行候选”，不能仅凭生成了树就称为全局最优解。