标签
讨论班
这个主题关联 9 篇内容。
约 2 分钟阅读 数学 词典序与普通最小生成树在单点度限制下的区别
我们采用“最大边优先”的词典序：比较两棵树 时，先比较 ；若相等，再比较 ，依此类推。
约 2 分钟阅读 数学 复杂度分析时间的主导来自一次全局排序与 Kruskal；其余操作为线性或近线性。
约 1 分钟阅读 数学 结论与展望本文针对单点度限制下的词典序最小生成树问题，提出了一种基于 Kruskal 构造初始最小生成森林； 一类/二类边的划分与优先级排序； 离线“指派”技术快速确定被替换的边。
约 1 分钟阅读 数学 问题定义无向连通图 ，其中 、； 每条边 的权值 ，且互不相同； 一个整数 （），要求最终生成树中顶点 的度数恰好为 。 一棵生成树 ，满足： ； 若记 的边权升序为。
约 1 分钟阅读 数学 相关工作与基础知识无度约束的最小生成树（MST）可在多项式时间内求解{cormen2009introduction}： Kruskal：边按权升序，能连通且不成环则加入，复杂度 {kruskal1956shortest}； Prim：从任一顶点出发，每次取跨割最小边，二叉堆实现为 {prim1957shortest}。
约 1 分钟阅读 数学 引言本文给出一个多项式时间的构造算法，并在后续证明其在可行域内的词典序最优性。
约 2 分钟阅读 数学 meta{词典序最小生成树；度限制生成树；单顶点度约束；贪心算法；图论}。
约 2 分钟阅读 算法 算法思路我们研究的目标是：在所有满足 的生成树中，使按从小到大排序的边权向量 在“最大边优先”的词典序下最小（先最小化 ，若相同再最小化 ，依此类推）。
约 3 分钟阅读 算法 正确性证明本章在边权互异的前提下，严格证明第~{sec:base-tree}~节与第~{sec:types}~节所述算法在 的可行域内输出“最大边优先”的词典序最小生成树，且最优解唯一。 {}{{maxlex}} 对生成树 ，记其边权从小到大排序为 。 给定两棵树 ，定义 当且仅当存在最小的 使得 且 。