《数学建模第七章图与网络方法建模--74通讯网络的最小生成树》由会员分享，可在线阅读，更多相关《数学建模第七章图与网络方法建模--74通讯网络的最小生成树（13页珍藏版）》请在金锄头文库上搜索。
1、$4通讯网络的最小生成树连通的无园图称为树。标是景简单但又是十分重要的一类图,它在许多学科领域中有广泛的应用,例如分子结构、电网络分析等。最短这接问题与树有关,学科分类和一些决策过恭也往仔可以用树的形式表示。若G是连通图G的生成子图,且G本身是树,则称G为G的生成树。对图G=(7.驭的每一条边ee5赋以相应的实数权w(e),得到一个网络,记为V=(.E厂,设7=(.E0)是N的一个生成树,后WC)-,则(称为7的权,中权最小的生成树称为V的最小生成树。许多实际问题,如在若干个城市之间建造铁路网、输电网或通信网等,都可归纳为寻求连通赋权图(网络的最小生成树问题。例如己知城市传和“间的直通线路的造
2、价为y井M(ey)(ey井(VioVj)要求一个总造价为最小的设计方案。又如一个城市中,对若干新建居民点供应自来水和煤气,已测知逊接各点间的直通管道的造价,要求给出一个总造价最小的铺设方案等等。下面介绍在给定网络N=(7.E厂)内求最小生成树的两种算法。设网络点数为九,此时最小生成树的边数为一1。算法1(克鲁斯凯尔,Kruskal)算法I的中心思想是每次添加权尽可能小的边,使新的图无啸,的到生成最小生成枪为止。也形象地简称“最小边的加入法“。其步骤如下:(1)把V内的所有边按照权的非减次序排列。(2)按(1排列的次序检查V中的每一条边,如果这条边与已得到的边不产生圈,则取这一条边为解的一部分。
3、(3)若己取到n-1条边,算法终止。此时以乙为顶点集,以取到的p-1条边为边集的图即为最小生成树。例1求图1所示网络的最小生成树。按各边的权的非减次序将网络中的8条边排列为口三白三三s首先取a和e为所求最小生成树7的两条边,然后检查边a。由于边a、。和a构成团,故不取边,考虑e。由于a、口和e不构成团,故可取a。然后检查纭o由于E】、6、龟和琉小构成卷故可取。此时由a、e、e和e构成的生成树7即为网络X的最小生成树(如图2)。算法2(普赖姆,Prim)这是一种迭代算法,每进行一次选代将产生组成网络N最小生成树7的一条边.其作法基于下面的弓宏实:如果我们已经知道7中的一些边,它们的端点集为$,则
4、5是X的顶点乙的一个子集。以e(5)记一个端点在5中、么一端点在1门3中的所有迅组成的集合,由于最小生成树7是V的连通生成子匹权最小的一条边,应该也是X的最小生成柄条边。,Q(S)门7中的一F面通过对图1所示的网络V求最优树7的过程介绍这一算法。算法开始时,5=(a),0(S)=(e,e:)。由于w(e)=1ov(e,)=2,取7=(e),并把a不在$中的一个端点古加入5中。于是5=(.m),Q(5)=(e.es.es.esa),0(3)中权最小的边为和a。任取一条迅,例卯e加入7中,把e不在3中的另一端点加进5中。此时7=(ese),5=0m:m),从而Q(8)=(a.e.e.es),其中权最小的边为e。&不在中的一个端点为,取新的r二帼判喇E(_】_z-_-)从而婀翰刮弗邬叫,其中权最小的边为e。e不在5中的一个端点为w,从而取7=(avecesse),s-6nmosw=7。此时以厂为顶点集,7teue:es:e)为边集的树7即为w的最小生成树。
