MST性质

MST性质就是最小生成树性质:

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

MST性质的证明

使用反证法证明。
假设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),T′也是G的一棵最小生成树,与假设矛盾