引言

问题背景

生成树是图论中的基本对象，在网络设计、通信、路由与其他组合优化问题中广泛出现\cite{cormen2009introduction}。 在实际应用里，我们常在“找一棵生成树”的基础上叠加约束，例如限制某个关键节点的度数以平衡负载，或在比较不同生成树时使用更细的优先级准则（如按词典序比较边权序列）。

研究对象

本文讨论带有单点度约束的词典序最小生成树：给定无向连通图、互异的边权，以及整数 $k$， 要求构造一棵生成树，使顶点 $1$ 的度数恰好为 $k$，并且在所有满足该约束的生成树中，它的边权序列（从小到大排列）在“最大边优先”的词典序下最小\cite{kahn2002lex}。 边权互异保证最优解唯一。

动机与意义

单点度约束把经典 MST 的贪心结构变得微妙：无约束时，词典序最小与加权和最小是等价的（Kruskal/Prim 都能得到同一解）；而一旦加入度约束，这两类目标便可能分叉，需要重新设计决策顺序与数据结构。此类模型可用于 - 通信／数据中心网络：限制核心设备的端口数； - 电力系统：限制主变电站的出线数量； - 树状索引或调度：限制根的分支数以降低维护开销。

本文给出一个多项式时间的构造算法，并在后续证明其在可行域内的词典序最优性。