单点度数约束生成树：问题与研究进展

作者：刘欣楠（Xinnan Liu），数学强基 2301。

英文题名：Lexicographically Minimal Spanning Trees with an Exact Single-Vertex Degree Constraint。

研究状态：待校订。 本专题保留一项算法研究的思路与推导。基树构造和固定入射边集合后的 Kruskal 补全可以独立验证；离线候选顺序的全局最优性尚未证明。原来的部分交换论证存在反例，详见证明校核。

问题与目标 #

给定无向连通简单图 $G=(V,E)$、互异边权及指定顶点 $1$，要求生成树满足 $\deg_T(1)=k$。 将树边按权值从大到小排列，从最大边开始逐项比较，目标是让第一个不同的权值尽可能小。 这是“最大边优先”的词典序目标，不是从最小边开始比较，也不能在有度数约束时直接改为最小化权值总和。

一般的多点度限制问题与这里的单点恰好度数问题不同；不能把一般问题的困难性或已有算法直接视为本专题的结论。

算法思路 #

先在删除顶点 $1$ 后的图中构造最小生成森林，并为每个连通分量选取一条最小权值的 $1$-边，得到度数为分量数 $r$ 的基树。 当 $k>r$ 时，研究稿尝试利用 Kruskal 合并过程记录候选边的离线排序键，选择 $k$ 条 $1$-边，再运行 Kruskal 补全生成树。

算法页保留各阶段的完整伪代码、输入检查和输出范围。该流程可以生成可行候选，但“候选即全局最优”仍需额外的交换不变量。

证据边界 #

• 复杂度页只分析已明确的排序、并查集和补全步骤，不把排序复杂度当作问题的理论下界。
• 目前本专题没有可复核的随机图、真实网络实验数据，也没有支撑 $10^5$ 条边性能结论的脚本与报告；原有相关实验结论不再作为研究成果列出。
• 小图核验可用于发现反例，不能替代一般正确性证明，也不能推导工程性能。

English Summary #

This research note studies spanning trees with an exact degree constraint at one designated vertex. Edge weights are compared lexicographically in non-increasing order, so the largest differing edge is decisive.

The candidate construction combines a minimum spanning forest, one root edge per component, an offline ordering of additional root edges, and a final Kruskal completion. Feasibility and the minimum-degree base case can be checked independently. Global optimality of the proposed offline ordering remains unproved; several earlier exchange arguments require correction. No reproducible performance study is currently included.

关键词 #

词典序最小生成树；单点度数约束；Kruskal；并查集；交换论证。

Lexicographically minimum spanning tree; exact single-vertex degree; Kruskal; disjoint-set union; exchange argument.