|
最小生成树 对于连通的带权图(连通网)G其生成树也是带权的生成树T各边的权值总和称为该树的权记作 这里: TE表示T的边集 w(uv)表示边(uv)的权 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)最小生成树可简记为MST 生成树和最小生成树的应用 生成树和最小生成树有许多重要的应用 【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市边表示两个城市之间的通信线路边上的权值表示线路的长度 或造价可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案 最小生成树性质(MST性质) ()MST性质 最小生成树性质设G=(VE)是一个连通网络U是顶点集V的一个真子集若(uv)是G中所有的一个端点在U(u∈U)里另一个端 点不在U(即v∈VU)里的边中具有最小权值的一条边则一定存在G的一棵最小生成树包括此边(uv) ()MST性质的证明 为方便说明先作以下约定 ①将集合U中的顶点看作是红色顶点②而VU中的顶点看作是蓝色顶点③连接红点和蓝点的边看作是紫色边④权最小的紫 边称为轻边(即权重最轻的边)于是MST性质中所述的边(uv)就可简称为轻边 用反证法证明MST性质 假设G中任何一棵MST都不含轻边(uv)则若T是G的一棵MST则它不含此轻边 由于T是包含了G中所有顶点的连通图所以T中必有一条从红点u到蓝点v的路径P且P上必有一条紫边(uv)连接红点集和蓝点集 否则u和v不连通当把轻边(uv)加入树T时该轻边和P必构成了一个回路删去紫边(uv)后回路亦消除由此可得另一生 成树T T和T的差别仅在于T用轻边(uv)取代了T中权重可能更大的紫边(uv)因为w(uv)≤w(uv)所以 w(T)=w(T)+w(uv)w(uv)≤w(T) 故T亦是G的MST它包含边(uv)这与假设矛盾 所以MST性质成立 求MST的一般算法描述 求MST的一般算法可描述为针对图G从空树T开始往集合T中逐条选择并加入n条安全边(uv)最终生成一棵含n条边的 MST 当一条边(uv)加入T时必须保证T∪{(uv)}仍是MST的子集我们将这样的边称为T的安全边 用伪代码可将算法描述为 GenerieMST(G){//求G的某棵MST T〈￠; //T初始为空是指顶点集和边集均空 while T未形成G的生成树 do{ 找出T的一条安全边(uv);//即T∪{(uv)}仍为MST的子集 T=T∪{(uv)}; //加入安全边扩充T } return T; //T为生成树且是G的一棵MST } 注意 下面给出的两种求MST的算法均是对上述的一般算法的求精两算法的区别仅在于求安全边的方法不同 为简单起见下面用序号…n来表示顶点集即 V(G)={…n} G中边上的权解释为长度并设T=(UTE) |
