迁移来源

• 旧站标题：相关工作
• 新站标题：图论与组合：讨论班 / 相关工作
• 旧站路径：/math/课程/图论与组合/chapters/讨论班/相关工作/
• 旧页面 ID：351

相关工作与基础知识

最小生成树的经典算法 #

无度约束的最小生成树（MST）可在多项式时间内求解\cite{cormen2009introduction}：

• Kruskal：边按权升序，能连通且不成环则加入，复杂度 $O(m\log m)$\cite{kruskal1956shortest}；
• Prim：从任一顶点出发，每次取跨割最小边，二叉堆实现为 $O(m\log n)$\cite{prim1957shortest}。

其正确性建立在切分性质与环性质之上；并查集（DSU）常用于维护连通性\cite{tarjan1975dsu}。

词典序最小与最小瓶颈 #

词典序最小生成树（LMST）要求按边权升序后的序列进行“最大边优先”的词典序比较。与之相关的最小瓶颈生成树（MBST）只最小化最大边\cite{camerini1978minmax}。无约束情形下，Kruskal 自然满足这两类目标的一致性。

度限制生成树 #

度限制生成树（DCMST）在 MST 上加入度约束。一般图上多点度上界是 NP-困难\cite{garey1979computers}；但在特定限制下存在多项式解或近似算法。单点度约束可作为一个相对简单而实用的情形，并已被系统研究\cite{narula1980dcmst}。

对本文的启发 #

单点度约束的常见做法是：先在除被限制顶点外构造生成森林，再通过与该顶点相连的边联通各块，必要时做边替换以满足度目标。本文在这一思路上叠加“最大边优先”的词典序目标，设计出能一次性确定候选顺序的实现方式。