瓶颈路证明

从删边形成切分出发，证明任意 MST 上的两点路径都是最小瓶颈路。

  • MST
  • 最小生成树
  • 瓶颈路
  • 图论

本文回答一个问题：最小生成树只要求整棵树的边权和最小，为什么它还能让任意两点之间路径上的最大边权最小？

算法背景见：最小生成树。这里仅展开瓶颈路性质的证明，不需要知道 MST 是由哪一种算法构造的。

要证明什么

设 G=(V,E)G=(V,E) 是无向连通带权图，TT 是其中任意一棵最小生成树，u,vu,v 是两个不同顶点。树上连接它们的唯一路径记为 PTP_T。

路径的瓶颈值，是路径上最大的边权：

B(P)=max⁡e∈Pw(e). B(P)=\max_{e\in P}w(e).

最小瓶颈路是使这个值尽量小的路径。我们要证明：对于原图中任意一条 uu 到 vv 的路径 PP，都有

B(PT)⩽B(P). B(P_T)\leqslant B(P).

因为 PTP_T 本身也是原图中的一条路径，这个不等式就说明它达到了最小瓶颈值。结论不要求边权互不相同，也不要求 MST 唯一。

先抓住直觉：删边后，另一条路也得过河

从 PTP_T 中挑一条最大权边 ee。删去它，树断成两部分，uu 和 vv 分别在两侧。

把这两个部分想成河的两岸：任何从 uu 走到 vv 的路径，都必须从一岸走到另一岸，至少经过一条跨越两侧的边。

如果整条替代路径的边都比 ee 轻，那么其中那条“过河”的边也比 ee 轻。用它接回两部分，就能降低整棵生成树的总权值。

因此，真正需要比较的不是两条路径的总长度，而是一条被删的树边与一条替代的跨越边。

详细证明

1. 假设存在瓶颈更小的路径

从 PTP_T 上任取一条最大权边 ee，于是

w(e)=B(PT). w(e)=B(P_T).

假设存在另一条 uu 到 vv 的路径 P′P'，满足

B(P′)<B(PT)=w(e). B(P')<B(P_T)=w(e).

这意味着 P′P' 上的每一条边都比 ee 轻。

2. 删去树边，得到两部分

从 TT 中删去 ee，得到两个连通分量，分别记为 SuS_u 和 SvS_v。

为什么 u,vu,v 一定分属两侧？因为 ee 位于树上连接它们的唯一路径中。如果删去 ee 后它们还连通，就说明树里原本存在另一条 uu 到 vv 的路径，与树上路径唯一矛盾。

所以，u∈Suu\in S_u，v∈Svv\in S_v；这两个集合覆盖所有顶点。

3. 替代路径必有一条跨越边

沿着 P′P' 从 uu 出发。起点在 SuS_u，终点在 SvS_v，因此它必然至少一次从 SuS_u 走到 SvS_v。

取其中一条跨越边 e′e'。它是 P′P' 上的边，所以

w(e′)⩽B(P′)<w(e). w(e')\leqslant B(P')<w(e).

注意：P′P' 可以与树路径共用部分边，不需要整条路径都由非树边组成。我们只需要其中一条跨越这次切分的边。

4. 换边，构造更轻的生成树

构造

T′=T−e+e′. T'=T-e+e'.

删去 ee 后，两部分各自都是树；e′e' 恰好连接这两个部分。因此加回 e′e' 后，全图重新连通，而且不会形成环，T′T' 是一棵合法的生成树。

它的总权值满足

w(T′)=w(T)−w(e)+w(e′)<w(T). w(T')=w(T)-w(e)+w(e')<w(T).

这与 TT 已经是最小生成树矛盾。因此，不存在瓶颈值严格小于 B(PT)B(P_T) 的路径，命题得证。

为什么不怕同权边和多棵 MST

反证时假设的是“严格更小”。如果替代路径的瓶颈与树路径相同，就不会构造出总权值严格更小的生成树，也不会产生矛盾；两条路径都可以是最小瓶颈路。

证明只使用了 TT 的最优性，没有使用它的构造方式或唯一性。因此，不同 MST 上的 uu 到 vv 路径可能不同，但路径的最大边权都等于同一个最小瓶颈值。

记住这条证明链

删最大边 → 两点分到两侧 → 更好的路径必有更轻的跨越边 → 换边后生成树更轻 → 矛盾。

这条推理把“两点路径是否最优”转成了“整棵生成树能否通过换边变得更轻”。

下面的图是假设存在更好路径时的局部示意：被删的树边权值为 10，假设路径中的跨越边权值为 5。如果真有这样的跨越边，原来的树就不可能是 MST，因为换边能降低总权值。

graph LR
    %% 节点样式定义
    classDef nodeStyle fill:#fff,stroke:#333,stroke-width:2px,color:black;

    %% 左边的连通分量 Su
    subgraph Su [集合 Su: 包含 u]
        direction TB
        u((u)):::nodeStyle
        u_end[节点 X]:::nodeStyle
        u_alt[节点 Y]:::nodeStyle

        %% 内部连接 (边索引 0)
        u === u_end
        %% 内部连接 (边索引 1)
        u -.- u_alt
    end

    %% 右边的连通分量 Sv
    subgraph Sv [集合 Sv: 包含 v]
        direction TB
        v((v)):::nodeStyle
        v_end[节点 Z]:::nodeStyle
        v_alt[节点 W]:::nodeStyle

        %% 内部连接 (边索引 2)
        v_end === v
        %% 内部连接 (边索引 3)
        v_alt -.- v
    end

    %% 核心冲突边
    %% (边索引 4) MST 上的最大边 e_max
    u_end == "e_max (权值: 10)" ==> v_end

    %% (边索引 5) 假设存在的更优边 e'
    u_alt -. "e' (权值: 5)" .- v_alt

    %% 样式应用
    %% 0, 2 是 MST 的树枝，设为黑色粗线
    linkStyle 0,2 stroke:black,stroke-width:3px;

    %% 1, 3 是假设路径 P' 的一部分，设为蓝色虚线
    linkStyle 1,3 stroke:blue,stroke-width:2px,stroke-dasharray: 5 5;

    %% 4 是红色的瓶颈边 e_max
    linkStyle 4 stroke:#ff0000,stroke-width:5px,color:red;

    %% 5 是绿色的更优边 e'
    linkStyle 5 stroke:#00cc00,stroke-width:4px,stroke-dasharray: 5 5,color:green;