图 - 生成树和最小生成树 - 最小生成树（一）
最小生成树
对于连通的带权图(连通网)G 其生成树也是带权的 生成树T各边的权值总和称为该树的权 记作
这里:
TE表示T的边集
w(u v)表示边(u v)的权
权最小的生成树称为G的最小生成树(Minimum SpannirngTree) 最小生成树可简记为MST
生成树和最小生成树的应用
生成树和最小生成树有许多重要的应用
【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市 边表示两个城市之间的通信线路 边上的权值表示线路的长度
或造价 可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案
最小生成树性质(MST性质)
( )MST性质
最小生成树性质 设G=(V E)是一个连通网络 U是顶点集V的一个真子集 若(u v)是G中所有的一个端点在U(u∈U)里 另一个端
点不在U(即v∈V U)里的边中 具有最小权值的一条边 则一定存在G的一棵最小生成树包括此边(u v)
( )MST性质的证明
为方便说明 先作以下约定
①将集合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性质成立
求MST的一般算法描述
求MST的一般算法可描述为 针对图G 从空树T开始 往集合T中逐条选择并加入n 条安全边(u v) 最终生成一棵含n 条边的
MST
当一条边(u v)加入T时 必须保证T∪{(u v)}仍是MST的子集 我们将这样的边称为T的安全边
用伪代码可将算法描述为
GenerieMST(G){//求G的某棵MST
T〈 ￠; //T初始为空 是指顶点集和边集均空
while T未形成G的生成树 do{
找出T的一条安全边(u v);//即T∪{(u v)}仍为MST的子集
T=T∪{(u v)}; //加入安全边 扩充T
}
return T; //T为生成树且是G的一棵MST
}
注意
下面给出的两种求MST的算法均是对上述的一般算法的求精 两算法的区别仅在于求安全边的方法不同
为简单起见 下面用序号 … n 来表示顶点集 即
V(G)={ … n }
G中边上的权解释为长度 并设T=(U TE)
lishixinzhi/Article/program/sjjg/201311/23829
AiPPT
2024-09-19 广告
