nan2inf .cn
算法 旧 .com 迁移

图论与组合：讨论班 / 算法思路

从旧 .com 全量搬运的历史内容，来源路径：/math/课程/图论与组合/chapters/讨论班/算法思路/

约 2 分钟阅读
migrationlegacy-comalgocourse-notecourse

迁移来源

算法思路

总体框架 #

我们研究的目标是：在所有满足 deg⁡T(1)=k\deg_T(1)=k 的生成树中，使按从小到大排序的边权向量 w(T)=(w[1](T)≤⋯≤w[n−1](T))\mathbf{w}(T)=(w_{[1]}(T)\le\cdots\le w_{[n-1]}(T)) 在“最大边优先”的词典序下最小（先最小化 w[n−1]w_{[n-1]}，若相同再最小化 w[n−2]w_{[n-2]}，依此类推）。

算法采取两阶段思路：

  • 基树阶段（仅用非 11-边 + 每块最小的 11-边）： 先在 V∖{1}V\setminus\{1\} 上用 E0:=E∖E1E_0:=E\setminus E_1 构造最小生成森林 F0min⁡F_0^{\min}；对每个连通块 CC 选取与 1 相连的最小边 bmin⁡(C)b_{\min}(C) 将其挂到 1 上，得到基树 Trmin⁡T_r^{\min}（此时 deg⁡(1)=r\deg(1)=r）。 若 k=rk=r 则返回。
  • 增添阶段（由一类边到二类边）： 当 k>rk>r 时，从剩余的 11-边中按“先能改进路径最大边者，再其余”的策略加入；每加入一条 11-边，都在新形成的环上删除路径上的最大边，直到 deg⁡(1)=k\deg(1)=k。

第二阶段的关键是对剩余 11-边进行类型划分与顺序选择，保证词典序意义下的全局最优。

\section{基树 Trmin⁡T_r^{\min} 的构造}

  • 在 V∖{1}V\setminus\{1\} 上对 E0E_0 按权值升序运行 Kruskal，得到最小生成森林 F0min⁡F_0^{\min}；其连通块记为 C1,…,CrC_1,\dots,C_r。
  • 对每个块 CiC_i 定义 bmin⁡(Ci)=arg⁡min⁡{ w(1,v)∣v∈Ci, (1,v)∈E }b_{\min}(C_i)=\arg\min\{\,w(1,v)\mid v\in C_i,\ (1,v)\in E\,\} （若不存在，则问题不可行）。
  • 令 T←F0min⁡∪{ bmin⁡(Ci)∣i=1,…,r }T\gets F_0^{\min}\cup\{\,b_{\min}(C_i)\mid i=1,\dots,r\,\} 即得 Trmin⁡T_r^{\min}，此时 deg⁡T(1)=r\deg_T(1)=r。若 k=rk=r，输出 TT。

直观上，F0min⁡F_0^{\min} 保证非 11-边部分的总体尽量小；而每块与 1 相连的最小边保证了跨割的最小性。后续会在正确性部分证明：这一步是任何可行解的必要选择（在词典序意义下）。

“一类/二类” 11-边与增添顺序 #

设当前生成树为 TT。对任意尚未被选用的 11-边 e=(1,x)e=(1,x)，记

MT(1,x):=max⁡{ w(f)∣f∈PT(1,x) }, M_T(1,x):=\max\{\,w(f)\mid f\in P_T(1,x)\,\},

其中 PT(1,x)P_T(1,x) 为 TT 中从 1 到 xx 的唯一路径。 将 ee 加入 TT 会形成唯一环，按最小生成树的环性质（最小情形）应删除环上最大边，也即删除 MT(1,x)M_T(1,x) 所对应的那条边。

据此把 ee 划分为：

  • 一类边（可改进）：若 w(e)<MT(1,x)w(e) < M_T(1,x)。加入 ee 并删除 MT(1,x)M_T(1,x) 会把更靠前的位置（较大的边）变小，从而在“最大边优先”的词典序下严格变优。
  • 二类边（会变差）：若 w(e)>MT(1,x)w(e) > M_T(1,x)。加入 ee 会把某个位置的值变大，词典序严格变差；只有在无一类边可用且必须提升度数时才考虑。

增添阶段的策略 #

当 deg⁡T(1)<k\deg_T(1)<k 时，反复执行：

  • 若存在一类边：选取使 MT(1,x)M_T(1,x)最大的一类边加入（从而优先降低更靠前的最大边），并删除路径上的最大边；
  • 否则：从二类边中选取 w(e)w(e)最小者加入，以最小化词典序的损失，同样删除路径上的最大边；

直至 deg⁡T(1)=k\deg_T(1)=k。这一顺序选择是后续正确性证明中的核心（“先一类后二类；一类内按被替换路径最大值降序；二类内按自身权值升序”）。

离线获得一类边的排序键：Kruskal + 并查集“指派” #

若直接在树上多次查询 MT(1,x)M_T(1,x) 并更新，代价较高。可以在构造 F0min⁡F_0^{\min} 的 Kruskal 过程中，顺带为一类边生成稳定的排序键，从而整体 O(mlog⁡m)O(m\log m)。

块内最小 11-边记录 #

在并查集（DSU）中维护每个连通块 B\mathcal{B} 的

m(B)=min⁡{ w(1,v)∣v∈B, (1,v)∈E }, m(\mathcal{B})=\min\{\,w(1,v)\mid v\in \mathcal{B},\ (1,v)\in E\,\},

若不存在与 1 相连的边则记为 +∞+\infty。

指派规则 #

当 Kruskal（升序）用某条 E0E_0-边 e0e_0 合并两个块 A,BA,B 时，设 a:=m(A)a:=m(A), b:=m(B)b:=m(B)，并令 a≥ba\ge b （交换 A,BA,B 可使之成立）。 在随后必须把两个块都“挂到 1”以满足连通性/度数的过程中， 较大的那条最小 11-边（即权值为 aa 的那条）被选入时，会在对应的环上删除 e0e_0。 因此把 e0e_0 指派给权值为 aa 的那条 11-边：记作 kill(a)=e0\mathrm{kill}(a)=e_0 ，并把 w(kill(a))w(\mathrm{kill}(a)) 视为该 11-边成为“一类边”时的排序键（即其将要“替换”的路径最大值）。

由指派得到顺序 #

对所有候选 11-边 e=(1,x)e=(1,x)，若 kill(e)\mathrm{kill}(e) 存在且 w(e)<w(kill(e))w(e)<w(\mathrm{kill}(e))，则 ee 为一类边，且应按 w(kill(e))w(\mathrm{kill}(e))从大到小排序；否则 ee 归入二类边，按 w(e)w(e)从小到大排序。 这样无需在线维护路径最大值，即可一次性得到第二阶段的选择顺序。

可行性与边界 #

必要条件：每个连通块至少有一条连到 1 的边，且 r≤k≤deg⁡G(1)r\le k\le \deg_G(1)。增添阶段每次“加一条 11 边、删环上最大边”，确保连通且最终度恰好为 kk。

伪代码 #

\begin{algorithmic}[1] \State **输入**：连通无向图 $G=(V,E)$，权 $w$，顶点 $1$，目标度数 $k$ \State **输出**：满足 $\deg_T(1)=k$ 的词典序最小生成树 $T$ \State **// 读取并拆分边：记录到 1 的最小边** \State 初始化 $\text{val}[v]\gets +\infty,\ \text{id}[v]\gets 0$ 对所有 $v$ \State $E_0\gets\varnothing$ \Comment{非 1 边} \For{每条边 $e=(x,y,w_e,\text{id}_e)\in E$} \If{$x=1$} \State $\text{val}[y]\gets\min(\text{val}[y],w_e)$,\ $\text{id}[y]\gets\text{id}_e$ \ElsIf{$y=1$} \State $\text{val}[x]\gets\min(\text{val}[x],w_e)$,\ $\text{id}[x]\gets\text{id}_e$ \Else \State $E_0\gets E_0\cup\{e\}$ \EndIf \EndFor \State **// 第一次 Kruskal（升序）：仅为计算 kill 值（记为 $\text{mx}[\cdot]$）** \State 将 $E_0$ 按权值 $\uparrow$ 排序；初始化 DSU：$\mathrm{fa}[v]\gets v$ \State $\text{mx}[v]\gets -\infty$ 对所有 $v$ \For{每条 $e=(u,v,w_e)\in E_0$（升序）} \State $x\gets \mathrm{find}(u),\ y\gets \mathrm{find}(v)$ \If{$x\neq y$} \If{$\text{val}[x] > \text{val}[y]$} \State 交换 $x,y$ \Comment{保证 $\text{val}[x]\le \text{val}[y]$} \EndIf \State $\mathrm{fa}[y]\gets x$ \State $\text{mx}[y]\gets w_e$ \Comment{把合并边指派给“较大的那条块内最小 1 边”} \EndIf \EndFor \State **// 组装 1 边候选序列 $tr$：前缀为各块的基边 $b_{\min}$** \State 压缩并查集；令 $p\gets 0$，$tr\gets [\,]$ \For{$v\in V\setminus\{1\}$} \If{$\mathrm{find}(v)=v$} \Comment{以根代表一个块 $C$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \State $\text{val}[v]\gets +\infty$；$p\gets p+1$ \EndIf \EndFor \State **// 一类 1 边：$\text{val}[v] < \text{mx}[v]$，按 $\text{mx}$ 降序** \For{$v\in V\setminus\{1\}$} \If{$\text{val}[v] < \text{mx}[v]$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \State $\text{val}[v]\gets +\infty$ \EndIf \EndFor \State 将 $tr[p+1\,..\,|tr|]$ 按 $\text{mx}[v]$ 降序排序；$p\gets |tr|$ \State **// 二类 1 边：余下的 $\text{val}$，按自身权值升序** \For{$v\in V\setminus\{1\}$} \If{$\text{val}[v] < +\infty$} \State 将 $(1,v,\text{val}[v],\text{id}[v])$ 追加到 $tr$ \EndIf \EndFor \State 将 $tr[p+1\,..\,|tr|]$ 按 $w$ 升序排序 \State **// 选择前 $k$ 条 1 边，并并到根 1；再用 $E_0$ 升序 Kruskal 补齐到 $n-1$** \State 重新初始化 DSU：$\mathrm{fa}[v]\gets v$ \For{$i \gets 1$ **to** $k$} \State $\mathrm{fa}[\,tr[i].y\,]\gets 1$ \EndFor \State $T\gets \{\,tr[1],\dots,tr[k]\,\}$ \For{每条 $e=(u,v,w_e,\text{id}_e)\in E_0$（与上相同的升序）} \State $x\gets \mathrm{find}(u)$，$y\gets \mathrm{find}(v)$ \If{$x\neq y$} \State $\mathrm{fa}[x]\gets y$ \State $T\gets T\cup\{e\}$ \EndIf \EndFor \State \Return $T$ \end{algorithmic}

小结 #

本章给出了算法的构造性蓝图：先以 F0min⁡ ⁣+ ⁣{bmin⁡}F_0^{\min}\!+\!\{b_{\min}\} 得到基树，再用“一类边优先、类内有序”的规则增添 11-边至恰好 kk 条；并通过 Kruskal+DSU 的“指派”机制离线获得一类边的排序键，使得实现层面维持在 O(mlog⁡m)O(m\log m) 的复杂度。

讨论

评论

正在加载评论...