最小生成树性质

最小生成树(MST)性质如下所述:

设
  连通网 G = (V, {E}),U 是 V 的非空真子集,(u, v) 是一端在 U,另一端在 V - U 的所有边中代价最小的边
则
  在 G 的所有最小生成树中,一定有一棵包含 (u, v)

证明

下面将使用反证法证明最小生成树性质。

假设 G 的所有最小生成树都不包含 (u, v),若 T 是 G 的最小生成树,则 T 不包含 (u, v)。在 T 中,一定存在一条边 (u′, v′) 连接 V - U 顶点集和 U 顶点集,该边一端在 U,另一端在 V - U。因为如果不存在这样的边,V - U 和 U 就无法连通,T 就不是生成树。

在下面的最小生成树 T 中,红色的顶点在 V 中,但是不在 U 中,蓝色的点在 U 中:

mst-1

将 (u, v) 加入到 T:

mst-2

此时会形成一个环:(u, u′, v′, B, v, u)

断开 (u′, v′),得到新的生成树 T′:

mst-3

cost(T′) = cost(T) + cost(u, v) - cost(u′, v′)

cost(u, v) <= cost(u′, v′)

故:

cost(T′) <= cost(T)

因此,T′ 也是 G 的一棵最小生成树,但是它包含 (u, v),与假设矛盾