最小斯坦纳树

概念

将指定点集中的所有点连通的树，称为斯坦纳树.

将指定点集中的所有点连通且边权总和最小的树，称为最小斯坦纳树 (Minimum Steiner Tree).

当指定点集与图的点集相等时，最小斯坦纳树等价于最小生成树.

问题

给定一个无向连通图 $G = (V,E)$，$n$ 个点，$m$ 条带权边，边权为正实数.

给定包含 $k$ 个点的点集 $S\subseteq V$，选出 $G$ 的子图 $G' = (V', E')$，使得

1. $S \subseteq V'$.
2. $G'$ 为连通图.
3. $E'$ 中所有边的权值和最小.

解法

定义

$T(i, X)$ 表示 $G$ 上以结点 $i$ 为根的一棵树，连通非空集合 $X$ 中所有点，且边权和最小.

图上的边权和函数 $C((V,E)) = \sum_{e\in E}{\mathrm{weight}(e)}$.

$T(i, X)$ 的边权和 $W(i, X) = C(T(i,X))$.

$\mathrm{dis}(i,j)$ 为 结点 $i$ 到 $j$ 的最短距离，以边权作为距离.

$P_{ij}$ 表示连接 $i$ 和 $j$ 的最短路径.

命题 1

$G'$ 必然为一棵树. $G'$ 是 $G$ 上连通 $S$ 的最小斯坦纳树.

证明：若存在重边和环，则去掉它们后，边权和变小且满足条件.

命题 2

移除 $G$ 上的自环和重边，$G'$ 不变.

证明: $G'$ 上不存在自环和重边.

命题 3

当 $|X|=1$，$X = \{j\}$ 时，$W(i, X) = \mathrm{dis}(i,j)$.

特别的，当 $i=j$ 时，$W(i, X) = \mathrm{dis}(i,i) = 0$.

证明: 根据定义，以 $i$ 为根且连通 $j$ 的 $T(i,\{j\})$ 是从 $i$ 到 $j$ 的最短路径.

命题 4

当 $|X|\ge 2$ 时

其中 $\{X_1,X_2\}$ 是 $X$ 的划分，且 $X_1\ne\emptyset$, $X_2\ne\emptyset$.

最小值取自所有这样的划分.

证明：合并两个子树可能产生重合边，使边权和增大，不是最优的.

命题 5

设 $I$ 是 $T(i,X_1)$ 和 $T(i,X_2)$ 的交集.

若存在 $\{X_1,X_2\}$ 使 $I = (\{i\},\emptyset)$，则

对所有这样的 $\{X_1,X_2\}$ 都成立.

证明：

当 $T(i,X_1)$ 和 $T(i,X_2)$ 仅交于结点 $i$ 时，合并两棵子树不会增加边权和.

由于两棵没有重合边的子树都是最优的，合并产生的 $T(i,X)$ 也是最优的. (最优子结构)

命题 6

最小值取自所有 $j \in V$.

证明：

$T_P = P_{ij}\cup T(j,X)$

$T_P$ 是 以 $i$ 为根 且 连通 $X$ 的树.

因此 $W(i,X)\le C(T_P)\le W(j,X)+ \mathrm{dis}(i,j)$ 对所有 $j\in V$成立.

命题 7

若存在 $j\in V$，使 $P_{ij}\cap T(j,X) = (\{j\},\emptyset)$，则

证明：

$T(j,X)$ 与 $P_{ij}$ 仅交于 $j$，$T(j,X)$ 是最优的，$P_{ij}$ 是最短的.

因此合并产生的 $T_P$ 以 $i$ 为根，连通 $X$，且边权和最小，符合 $T(i, X)$ 定义.

$T(i, X) = T_P$

$W(i,X) = C(T_P)$

$C(T_P) = W(j,X)+ \mathrm{dis}(i,j)$

命题 8

对于确定的 $i$ 和 $X$，以下三个推断至少有一个成立.

1. $|X| = 1$
2. 存在 $\{X_1,X_2\}$ 使 $T(i,X_1) \cap T(i,X_2) = (\{i\},\emptyset)$. (命题 5)
3. 存在 $j\in V$，使 $P_{ij}\cap T(j,X) = (\{j\},\emptyset)$. (命题 7)

证明：

当 $|X|=1$ 时，推断 1 成立，其余情况满足 $|X|\ge 2$ 且推断 1 不成立.

1. 若 $i$ 是割点

   设 $i$ 将 $G$ 切割为 $h$ 个连通分量，按顺序标记为 $C_1,C_2,\dots,C_h$.

   则构造划分 $\{X_1,X_2\}$，

   $$X_1 \subseteq V(C_1\cup \{i\})$$$$X_2\subseteq V(C_2\cup C_3 \cup \dots \cup C_h)$$$$T(i,X_1) \cap T(i,X_2) = (\{i\},\emptyset)$$

   推断 2 成立.

2. 若 $i$ 不是割点

   记 $G$ 上 以 $i$ 为端点的边 的集合为 $E_i$.

   记 $G$ 移除结点 $i$ 和 以 $i$ 为端点的边 后的子图为 $G_i$.

   $$G_i = (V-\{i\},E-E_i)$$

   取 $i$ 的邻接点 $j$. $T_{G_i}(j, X - \{i\})$ 表示 $G_i$ 上以结点 $j$ 为根的一棵树，连通 $X - \{i\}$ 中所有点，且边权和最小.

   由于边权为正实数，从 $({i},E_i)$ 中选取部分加入 $T_{G_i}(j, X - \{i\})$ 不可能使边权和变小，因此

   $$T(j,X - \{i\}) = T_{G_i}(j, X - \{i\})$$

   选取 $E_i$ 中具有最小权值的边 $e_{ij}$，它的端点为 $i$ 和 $j$，加入 $T(j,X - \{i\})$，得 $T(i,X)$，它一定是最优的.

   • 当 $i\notin X$ 时

     $$T(j,X - \{i\}) = T(j,X)$$$$P_{ij}\cap T(j,X) = (\{j\},\emptyset)$$

     此时推断 3 成立.

     示例：

   • 当 $i\in X$ 时，令 $X_1=\{i\},X_2=X-\{i\}$，

     $$T(j,X - \{i\}) = T(j,X_2)$$$$T(i,X_1) = (\{i\},\emptyset)$$$$T(i,X_2) = (\{i\}, \{e_{ij}\}) \cup T(j,X_2)$$$$T(i,X_1) \cap T(i,X_2) = (\{i\},\emptyset)$$

     此时推断 2 成立.

命题 9

证明：

由命题 3 导出，当 $|X|=1$，$X = \{j\}$ 时，

其中 $W(i,\{i\}) = W(i,\{i\}) + dis(i,i)$ 为递归不动点，需要指定 $W(i,\{i\}) = 0$.

当 $|X|\ge 2$ 时，命题 8 中推断 2 和 3 至少有一个成立.

由命题 4 和 5 导出等式 1:

由命题 6 和 7 导出等式 2:

等式 1 和 2 至少有一个成立.

由于 $W(i, X)$ 有全局最优值，命题 9 成立.

算法

使用动态规划，在 $X$ 计算之前，$X$ 的子集必须计算完毕，先初始化单元素集合，再依次上推，得到 $W(i,S)$.

假设子集结果已经求出。

转移方程1

转移方程2

由于第一步转移得到的不一定是最优值，将临时结果记为 $W'(i,X)$

• 其中至少有一个 $W'(i,X)$ 会达到全局最优值.

证明：若 $G$ 中有割点，当 $i$ 为割点时成立，若 $G$ 中没有割点，当 $i\in X$ 时成立。

考虑新建一个虚拟源点 $v$，向 $V$ 中每个点 $i$ 连一条有向边，$\mathrm{weight}(e_{vi}) = W'(i,X)$，其中 $W'(i,X)$ 是第一步的结果.

转移方程 2 相当于三角不等式，可用松弛操作。比较两种类型的方案，从 $v$ 直接走到 $i$，或者从$v$走到某个点 $j$，再通过最短路径走到 $i$，其中 $j\in {V-\{i\}}$.

第二步结果相当于计算 $v$ 到每个点 $i$ 的最短距离，可以使用单源最短路算法.

第二步的另一种转移法是 预计算 $dis$，直接枚举 $(i,j)$，更新 $n^2$ 次，当 预计算开销 + $n^2$ 小于最短路开销时可用。

• 第二步结果 $W''(i,X)$ 一定会收敛到 $W(i,X)$.

证明：

当 $W'(i,X) = W(i,X)$ 时，第二步不会改变它，已收敛.

当 $W'(i,X)>W(i,X)$ 时，推断 2 不成立，推断 3 必然成立，即存在某点使 $W''(i, X)$ 收敛到 $W(i,X)$.

转移完成后得该层 $W(i,X)$，能够继续向上转移。

对于所有 $i\in S$，$T(i,S)$ 相同，是最小斯坦纳树，$W(i,S)$ 是所求边权和.

复杂度

使用堆优化 Dijkstra 算法求单源最短路，时间 $O(m\mathrm{log}(m))$，也可以用其他算法.

$X$ 的子集数不超过 $2^{|X|}$，$X\subseteq S$，$|S| = k$. 使用状态压缩.

第一步的计算次数不超过 $n\cdot\sum_{1\le i\le k}{2^i \binom{k}{i} }= (3^k-1)n$. (二项式定理)

第二步的计算次数不超过 $2^k\cdot m\mathrm{log}(m)$.

总时间复杂度 $O(3^kn+2^km\mathrm{log}(m))$.

如果第二步使用预计算+直接更新，通常是 Floyd 算法，那么总时间为 $O(3^kn+n^3+2^kn^2)$.

斯坦纳森林

问题

在相同的 $G$ 上，给定 $h$个互不相交的集合 $S_1,S_2,S_3,\dots,S_h$，求出使 $S_i (1\le i\le h)$ 内所有点连通且边权和最小的子图. 子图可以不连通.

解法

设 $S_H = \{ S_1,S_2, S_3,\dots,S_h\}$

考虑 $S_H$ 的某个划分，对划分的一个子集，将它的所有元素取并集 ，对这个划分做这样的映射，记结果为$S_{H'}$.

示例: $\{\{S_1,S_2\}, \{S_3,S_4\}\}$ 映射为 $\{S_1\cup S_2,S_3\cup S_4\}$.

$S_{H'}$ 的每个元素对应一个 $G$ 上连通它的最小斯坦纳树，所求子图是这样的所有最小斯坦纳树合并形成的森林 (或树).

• 证明

  考虑 连通 $S_1$ 的最小斯坦纳树 与 连通 $S_{2}$ 的最小斯坦纳树.

  如果两者没有重合边，那么组成的森林是最优的，如果两者有重合边，那么可以用连通 $S_1\cup S_2$ 的最小斯坦纳树替换它.

  当所有 连通 $S_i (1\le i\le h)$ 的最小斯坦纳树加入之后，所得森林 (或树) 与上述的等效，并且是最优的.

设 $S= S_1\cup S_2\cup S_3\cup \dots\cup S_h$，$|S| = k$，可求出所有的 $W(i,X)$.

方法 1

暴力枚举 $S_H$ 集合的所有划分，对每个划分，求映射得到的所有最小斯坦纳树的边权和的总和，对所有划分求最小值.

如果某个划分是最优方案，那么它会留下，如果它不是最优的，说明斯坦纳树之间有重合边，替换成连通并集的斯坦纳树即可，而替代方案一定在所有划分之中.

集合的划分数是一个指数增长的数列 (OEIS A000110). ($B(4)=15,\,B(5)=52$).

枚举划分是个比较麻烦的事，可以用 $2^{h^2}h$ 的状压过滤来实现，也可以寻找更方便快速的算法.

状压过滤后，每次求最小值需要 $h$ 的时间，因此求森林时间为 $O(2^{h^2}h^2)$.

方法 2

设 $H(X)$ 是 连通 $X$ 中具有相同分类的点且边权和最小的森林 (或树) 的边权和. 显然 $H(S)$ 是答案.

仅当 $(X \cap S_i =\emptyset) \vee (X \cap S_i =S_i)$ 为真时，$X$ 是有效的.

示例：$S_1=\{1,2\},\,S_2=\{3,4\}$，此时 $X=\{1,2,3\}$ 是无效的，因为 $3$ 与 $4$ 不连通.

枚举 $S$ 的所有有效子集 $X$，枚举 $X$ 的有效非空子集 $X_1$，$X_2=X-X_1$.

根据上面的证明过程写出转移方程.

当 $|X|=1$ 时，$H(X)=0$.

如果使用状压检验 $X$ 是否有效，那么检验时间为 $h$.

最终求森林时间为 $O(2^kn+3^kh)$.

题目

洛谷 P6192

https://www.luogu.com.cn/problem/P6192

最小斯坦纳树 模板 完整代码

POJ-3123

https://vjudge.net/problem/POJ-3123

斯坦纳森林

HDU-4085

https://vjudge.net/problem/HDU-4085

斯坦纳森林 完整代码

$n$ 个点，$m$ 条边，无向图. 前 $k$ 个点是村民，后 $k$ 个点是避难所.

选择具有最小边权和的子图，使子图的每个连通块中村民和避难所的数量相等，并且所有村民都在子图中.

将村民和避难所设为关键点，$|S| =2k$.

设 $H(X)$ 是 对 $X$ 满足要求且边权和最小的森林 (或树) 的边权和. 显然 $H(S)$ 是答案.

当 $X$ 中的村民和避难所的数量相等时，$X$ 有效.

如果 $H(X)$ 对应的子图有多个连通块，那么它能从两个最优的子图合并而来.

如果 $H(X)$ 对应的子图只有一个连通块，那么它一定是连通 $X$ 的最小斯坦纳树.

当 $|X| = 2,\,H = \{i,j\}$ 时，$H(X) = dis(i,j) = W(i,X)$，达到最优.

递推可知，如果 $X$ 的所有子集在 $X$ 之前转移完成，那么 $H(X)$ 是最优的.

最后输出 $H(S)$.

HDU-3311

https://vjudge.net/problem/HDU-3311

斯坦纳森林

HYSBZ-2595

https://vjudge.net/problem/HYSBZ-2595

四连通二维矩阵，权值变为点，特殊处理