单点度约束生成树：问题定义与比较示例

输入与输出 #

输入 #

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

仅有上述整数范围并不保证存在可行树。例如星形图中，中心顶点在任何生成树中的度都只能等于 $n-1$。

输出 #

若不存在满足 $\deg_T(1)=k$ 的生成树，返回不可行。否则，输出一棵可行生成树 $T=(V,E_T)$，并要求它在以下“最大边优先”的词典序下最优。

将一棵树的边权按升序记为

$$\mathbf{w}(T)=(w_{[1]}(T),\ldots,w_{[n-1]}(T)), \qquad w_{[1]}(T)<\cdots<w_{[n-1]}(T).$$

固定输出树 $T$。对每棵与它不同的可行树 $T'$，从序列末尾开始比较；设 $t\in\{1,\ldots,n-1\}$ 是第一个出现差异的位置，即

$$t=\min\{s:w_{[n-s]}(T)\ne w_{[n-s]}(T')\}.$$

要求 $w_{[n-t]}(T)<w_{[n-t]}(T')$。等价地，先比较最大边，若相同再比较次大边，直到出现差异。这不等于比较边权总和，也不是从最小边开始的普通升序词典序。

边权互异使不同边集具有不同的权值序列；有限非空可行集在该全序下恰有一个最小元素，因此最优树唯一。本节只规定优化目标，不据此断言某个具体构造算法正确。

说明性示例 #

设 $V=\{1,2,3,4\}$，边集恰由下表五条边组成：

边	权值	说明
$(1,2)$	1	与 1 相连
$(1,3)$	5	与 1 相连
$(2,3)$	2	非 1 边
$(2,4)$	3	非 1 边
$(3,4)$	4	非 1 边

取 $k=1$，可行树必须在与 $1$ 相连的两条边中恰选一条，再从 $\{(2,3),(2,4),(3,4)\}$ 中选两条以连接其余三个顶点。

若选 $(1,3)$，最大边权一定为 $5$。若选 $(1,2)$，其余两条边的三种选择给出下面的升序序列：

其余两条边	升序边权序列	最大边优先的比较
$(2,3),(2,4)$	$(1,2,3)$	最大边为 3，最优
$(2,3),(3,4)$	$(1,2,4)$	最大边为 4
$(2,4),(3,4)$	$(1,3,4)$	最大边为 4，次大边也更大

因此唯一最优树为

$$E_T=\{(1,2),(2,3),(2,4)\},\qquad \mathbf{w}(T)=(1,2,3).$$

它连通、无环，并且顶点 $1$ 的度恰为 $1$。这个结论由完整的六种可行选择比较得到，不依赖尚未在本节讨论的算法。