最小生成树(MST)的性质及算法 [转】

时间:2022-09-14 19:05:23

转自:

chensohg的博客

http://blog.sina.com.cn/u/1182060252

最小生成树性质1:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中,具有最小权值的一条边,则一定存在G的一棵最小生成树包括此边(u,v)。

证明:
为方便说明,先作以下约定:
  ①将集合U中的顶点看作是红色顶点,②而V-U中的顶点看作是蓝色顶点,③连接红点和蓝点的边看作是紫色边,④权最小的紫边称为轻边(即权重最"轻"的边)。于是,MST性质中所述的边(u,v)就可简称为轻边。
  用反证法证明MST性质:
  假设G中任何一棵MST都不含轻边(u,v)。则若T是G的一棵MST,则它不含此轻边。
由于T是包含了G中所有顶点的连通图,所以T中必有一条从红点u到蓝点v的路径P,且P上必有一条紫边(u',v')连接红点集和蓝点集,否则u和v不连通。当把轻边(u,v)加入树T时,该轻边和P必构成了一个回路。删去紫边(u',v')后回路亦消除,由此可得另一生成树T'。
T'和T的差别仅在于T'用轻边(u,v)取代了T中权重可能更大的紫边(u',v')。因为w(u,v)≤w(u',v'),所以 w(T')=w(T)+w(u,v)-w(u',v')≤w(T)
故T'亦是G的MST,它包含边(u,v),这与假设矛盾。
所以,MST性质成立。

最小生成树性质2:其最大边权为生成树中最大边权最小的。

证明
反证法:假设Ta为一棵最小生成树,Tb为一棵非最小生成树且其最大边权小于Ta的最大边权。
e是最小生成树Ta的最大边,e将最小生成树Ta分为连通的2个部分A->B,Tb的连接A->B的边权为e1,e1<=eb(Tb上最大边权)<e,即A->B之间存在一条权值比e更小的连通A和B的边,故Ta不是最小生成树,矛盾,故假设不成立。

==========================================================================
Prim算法与Kruskal算法是寻找最小生成树的经典方法,两者皆为贪心法,一次“生成”一条“安全边”,如下所示:

GENERIC-MST-FUNCTION (G,w)
1 T := 空集合
2 while T 还不是生成树
3 do 找出对 T 来说是不会形成cycle,且权重最低的边 (u, v)
4 T := T U {(u, v)}
5 return T