斯坦纳树问题

斯坦纳树问题（Steiner tree problem）要求以最小总成本连接一组指定终端，并允许使用额外的中转顶点。它与最小生成树的区别在于：必须连接的是终端集合，而不是把给定图的每一个顶点都接入。

在一个教学网络中，三个终端 $A, B, C$ 之间各有费用四的直接边，另有可选中转点 $O$ ，连向三个终端的边各费用二。只用终端之间的边，需要两条、费用八；采用中转点的三条边，总费用六。增加中转点使边数变多，却能减少总成本。这里的费用是图的输入，不按示意图上的直线长度量取。

图上的终端连接模型

设 $G = (V, E)$ 是有限无向图，边权 $w_{e} \geq 0$ ，终端集合 $\emptyset \neq T \subseteq V$ 。寻找包含全部 $T$ 的连通子图，使所用边权之和最小。非负性保证可以删掉环而不增加成本，因此总能在树中取得一个最优解；非终端叶子也可删去，所以存在一个没有多余非终端叶子的最优树。^[1]

当 $T = V$ 时退化为最小生成树；只有一个终端时，零边、费用零即可；若终端分处原图不同连通分量，则无解。原图中的可选顶点不必全部使用。把所有顶点先做一棵最小生成树再删叶，虽能给出某个连接方案，却不能由此保证最优。

三个终端的直接三角边权四，中转点O到各终端边权二；比较终端树八与中转树六 — 图的边权是给定成本，屏幕距离不代表费用。实线选择三条中转边，终端仍只有 A、B、C。

枚举可选顶点的精确原理

对每个 $S \subseteq V ∖ T$ ，取诱导子图 $G [T \cup S]$ 。若它连通，求其最小生成树成本。遍历所有 $S$ ，取最小成本，便得到图上斯坦纳树的最优值。

证明。 每个枚举出的生成树都连通全部终端，所以是原问题的可行解，其费用不可能低于原最优值。反过来，取某个最优斯坦纳树 $H$ ，令它实际使用的非终端集合为 $S^{*}$ 。枚举必定遇到 $S^{*}$ ； $H$ 是诱导子图 $G [T \cup S^{*}]$ 内的一棵生成树，故该子图的最小生成树费用不高于 $H$ 。两方向合起来，最小枚举费用恰好等于最优值。

这里诱导子图保留这些顶点之间所有可用边，并不要求把这些边全选入。求生成树时仍会在边之间选择，所以“枚举顶点”与“把所有诱导边直接相加”是不同的算法。

开头例子只有一个可选顶点。 $S = \emptyset$ 时成本八； $S = {O}$ 时三条费用二的边形成成本六的生成树，所以精确最优为六。若把 $O C$ 的费用改为六，使用 $O A, O B$ 加一条连向 $C$ 的费用四直接边，总费用也为八；中转点的存在不再带来严格改进。这是一个有解变式，说明可选不等于必选。

小图精确实现

以下代码适用于有限无向简单图，顶点编号 $0, \dots, n - 1$ 。边权为非负整数或 Fraction；终端为非空、无重复的合法编号。函数返回成本及树边，若没有连通所有终端的方案则返回 None，不修改输入。

Python 3

from fractions import Fraction


def steiner_small(n, edges, terminals):
    if type(n) is not int or n < 1:
        raise ValueError("n must be positive")
    target = tuple(terminals)
    if (not target or len(set(target)) != len(target)
            or any(type(v) is not int or not 0 <= v < n for v in target)):
        raise ValueError("Invalid terminals")
    weighted, seen = [], set()
    for u, v, weight in edges:
        if type(u) is not int or type(v) is not int:
            raise TypeError("Integer vertex labels required")
        if not (0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("Invalid edge")
        if isinstance(weight, bool) or not isinstance(weight, (int, Fraction)):
            raise TypeError("Use integer or Fraction weights")
        edge, w = (min(u, v), max(u, v)), Fraction(weight)
        if w < 0 or edge in seen:
            raise ValueError("Nonnegative simple edges required")
        seen.add(edge)
        weighted.append((w, u, v))
    weighted.sort()
    target = set(target)
    optional = [v for v in range(n) if v not in target]
    best = None
    for mask in range(1 << len(optional)):
        allowed = target | {v for j, v in enumerate(optional) if mask >> j & 1}
        parent, rank = list(range(n)), [0] * n

        def find(v):
            while parent[v] != v:
                parent[v] = parent[parent[v]]
                v = parent[v]
            return v

        chosen, cost = [], Fraction(0)
        for w, u, v in weighted:
            if u not in allowed or v not in allowed:
                continue
            a, b = find(u), find(v)
            if a == b:
                continue
            if rank[a] < rank[b]:
                a, b = b, a
            parent[b] = a
            if rank[a] == rank[b]:
                rank[a] += 1
            chosen.append((u, v, w))
            cost += w
        if len(chosen) == len(allowed) - 1:
            if best is None or cost < best[0]:
                best = cost, tuple(chosen)
    return best


network = [(0, 1, 4), (1, 2, 4), (2, 0, 4),
           (3, 0, 2), (3, 1, 2), (3, 2, 2)]
print(steiner_small(4, network, [0, 1, 2])[0])
# 6

内层按权重从小到大接入连接不同分量的边，即 Kruskal 方法。为何不会漏掉更好的生成树？每次接入的边横跨当前森林的一个分量与其外部。在任何含当前已选森林的最优生成树中，若这条边不在树里，加入它形成的环必含另一条跨同一分割的边；该边权不小于当前所选边。交换后成本不增，并保留此前森林。归纳至选满生成树，便证明内层最优；外层最优性已由顶点枚举证明。

设有 $r = | V ∖ T |$ 个可选顶点、 $m$ 条边。全局排序一次，随后运行 $2^{r}$ 次并查集扫描。采用按秩合并及路径压缩，时间可写为 $O (m \log m + 2^{r} (n + m α (n)))$ ，其中 $α$ 是反阿克曼函数，边权精确算术的位成本另计；工作空间为 $O (n + m)$ 。可选顶点变多时指数枚举很快失去实用性，代码只用于小图复核，不是大规模网络求解器。

平面上允许新增位置的另一种模型

欧氏斯坦纳树允许在平面任意位置新增连接点，边费是实际线段长度；这与前面的有限图模型不同，可选位置不再来自一个有限顶点清单。^[2]

对三条线段连接的内部新点 $x$ ，目标为 $F (x) = | x - A | + | x - B | + | x - C |$ 。若 $x$ 不与终端重合且是驻点，求梯度得 $\frac{x - A}{| x - A |} + \frac{x - B}{| x - B |} + \frac{x - C}{| x - C |} = 0.$ 三个单位向量相加为零。将其中两个移到一侧再平方，得到每一对内积为 $- 1 / 2$ ，所以三条线段两两夹角为 $12 0^{\circ}$ 。这个条件针对内部的三分支点，不能强加在原终端上。

边长二的等边三角形中，中心到三个顶点长度均为二除以根号三，中心三角均为一百二十度 — 本图采用欧氏长度，中心三分支总长为 2√3，小于只使用两条边的生成树长度四。它与前图的任意给定边权是不同模型。

边长二的等边三角形，中心 $O$ 到每个顶点距离为 $r = 2 / \sqrt{3}$ ，三条单位方向相加为零。对任意点 $x$ ，单位向量的投影不超过长度，故 $| x - A | \geq \frac{O - A}{r} \cdot (x - A) = r + \frac{O - A}{r} \cdot (x - O) .$ 对三个终端相加，最后的线性项抵消，得到 $F (x) \geq 3 r = 2 \sqrt{3}$ ，中心达到下界。三终端的任何树形连接，删去多余叶子、将二度中转链用直线替代后，至多剩一个三分支点，或分支退化到一个终端；这些都包含在上述星形比较中，所以该下界也给出此三终端问题的最优值。

有限图代码不能处理平面任意新位置；把图画得像等边三角形，也不能让给定图权自动变成欧氏长度。先区分可用边、可选点及成本定义，才能比较不同模型的结果。

参考资料

↑ NetworkX：steiner_tree，官方文档中的终端最小权连接树定义及近似方法说明。本文的可选顶点枚举实现独立编写，是小图精确方法，不是该库近似算法的改写。访问日期：2026年10月25日。
↑ Amedeo R. Odoni：Networks: Lecture 1，MIT 1.203J，2006，PDF第10–12页“MST vs. Steiner Problem in the Euclidean Plane”。

[nx-1] NetworkX：steiner_tree，官方文档中的终端最小权连接树定义及近似方法说明。本文的可选顶点枚举实现独立编写，是小图精确方法，不是该库近似算法的改写。访问日期：2026年10月25日。

[2] Amedeo R. Odoni：Networks: Lecture 1，MIT 1.203J，2006，PDF第10–12页“MST vs. Steiner Problem in the Euclidean Plane”。

[1]

[2]