迁移来源

• 旧站标题：问题定义
• 新站标题：图论与组合：讨论班 / 问题定义
• 旧站路径：/math/课程/图论与组合/chapters/讨论班/问题定义/
• 旧页面 ID：355

问题定义

输入与输出 #

输入 #

• 无向连通图 $G=(V,E)$，其中 $|V|=n$、$|E|=m$；
• 每条边 $e\in E$ 的权值 $w(e)\in\mathbb{R}$，且互不相同；
• 一个整数 $k$（$1\le k\le n-1$），要求最终生成树中顶点 $1$ 的度数恰好为 $k$。

输出 #

一棵生成树 $T=(V,E_T)$，满足：

• $\deg_T(1)=k$；
• 若记 $T$ 的边权升序为

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

则在所有满足 (1) 的生成树中，$\mathbf{w}(T)$ 在“最大边优先”的词典序下最小： 对任意可行 $T,T'$，若存在最小 $t$（从末尾计数）使得 $w_{[n-t]}(T)\neq w_{[n-t]}(T')$，则要求 $w_{[n-t]}(T)<w_{[n-t]}(T')$。

说明性示例 #

设图包含以下边（边权互异）：

`latex

\begin{tabular}{c|c|c} 边 & 权值 & 说明 \\ \hline (1,2) & 1 & 与 1 相连 \\ (1,3) & 5 & 与 1 相连 \\ (2,3) & 2 & 非 1 边 \\ (2,4) & 3 & 非 1 边 \\ (3,4) & 4 & 非 1 边 \\ \end{tabular}

`

若 $k=1$，可行树必须在与 1 相连的边中恰选一条。比较不同可行树时，先看最大边，若相同再看次大边，依此类推，最终唯一确定最优解。