最小生成树模型与实验.docx

《最小生成树模型与实验.docx》由会员分享，可在线阅读，更多相关《最小生成树模型与实验.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树模型与实验第六章最小生成树模型与实验树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。6.1树与树的性质上章已讨论了图和树的简单基本性质。为使更清楚明了，如今使用实例来讲明。例6.1已知有五个城市，要在它们之间架设电话线，要求任何两个城市都能够相互通话允许通过其它城市，并且电话线的根数最少。用五个点54321,vvvvv代表五个城市，假如在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就能够用一个图来表示。为了任何两个城市都能够通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图还是连

2、通的，这样能够省去一根电话线。因此，知足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式知足要求的一个电话线网。定义6.1一个无圈的连通图称为树.例6.2某大学的组织机构如下所示:v5v4v图6.1教务处研究处校行政办公室研究生院财务科行政科理工学院人事学院外语学院假如用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。树的性质：1树必连通，但无回路圈；2n个顶点的树必有1-n条边；3树中任意两点间，恰有一条初等链；4树连通，但去掉任一条边，必变为不连通；5树无回路圈，但不相邻顶点连一条边，恰得一回路圈。生

3、成树与最小树定义6.2设图),(11EVG=是图,EVG=的生成子图，假如1G是一棵树，记),(1EVT=，则称T是G的一棵生成树。定理6.1图G有生成树的充分必要条件是图G的连通的。数学系物理系文科办公理科办校教学办公室校长证：必要性是显然的充分性：设G是连通图。i假如G不含圈，由定义6.1可知，G本身就是一棵树，进而G是它本身的生成树。ii假如G含圈，任取一圈，从圈中任意去掉一条边，得到图G的一个生成子图1G，假如1G不含圈，那么1G是G的一棵生成树由于易见1G是连通的；假如1G仍含少量圈，那么从1G中任取一个圈，从圈中再任意去掉一条边，得到图G的一个生成子图2G，如此重复，最终能够得到G

4、的一个生成子图kG，它不含圈，则kG是图G的一棵生成树。6.2最小生成树的实例与求解由以上充分性的证实中，提供了一个寻求连通图的生成树的方法，称这种方法为“破圈法。例6.4在图6.1中，用破圈法求出图的一棵生成树解：取一圈1233211vevevev去掉3e；取一圈123544211vevevevev去掉5e；取一圈2657442vevevev去掉7e；取一圈123856211vevevevev去掉6e；如图6.3所示，此图是图6.2的一个生成子图，且为一棵树无圈，所以我们找一棵生成树,11EVT=，其中，,82411eeeeE=。不难发现，图的生成树不是唯一的，对于上例若这样做：v5v3图6

5、.2取一圈1233211vevevev去掉3e；取一圈123554211vevevevev去掉4e；取一圈123856211vevevevev去掉6e；取一圈4538574vevevev去掉8e。图6.3图6.4如图G的生成树还有另外一种方法“避圈法，主要步骤是在图中任取一条边1e，找出一条不与1e构成圈的边2e，再找出不与,21ee构成圈的边3e。一般地，设已有,21keee，找出一条不与,21keee构成圈的边1+ke，重复这个经过，直到不能进行下去为止。这时，由所有取出的边所构成的图是图G的一棵生成树。定义6.2设,EVT=是赋权图,EVG=的一棵生成树，称E中全部边上的权数之和为生成树

6、T的权，记为)(Tw。即=TvvijjiwTw,)(。(7.1)假如生成树*T的权)(*TW是G的所有生成树的权中最小者，则称*T是G的最小生成树，简称为最小树。即)(min)(*TwTwT=7.2式中对G的所有生成树T取最小。求最小树通常用下面两种方法。1破圈法：在给定连通图G中，任取一圈，去掉一条最大权边假如有两条或两条以上的边都是权最大的边，则任意去掉其中一条，在余图中是图G的生成子图任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图G的最小树。例6.4用破圈法求图6.5的最小树。图6.5是一赋权图。,211vve=，1)(1=ew；,312vve=，4)(2=ew；,

7、323vve=，2)(3=ew，,424vve=，3)(4=ew；,435vve=，1)(5=ew；,526vve=，5)(2=ew，,547vve=，2)(7=ew；,528vve=，3)(8=ew。解：取一圈1233211vevevev去掉2e；取一圈2338562vevevev去掉6e；取一圈2335442vevevev去掉8e；取一圈4538574vevevev去掉8e。如图6.6所示，得到一棵生成树，即为所求最小树*T，62121)(*=+=Tw。2避圈法(Kruskal算法)：在连通图G中，任取权值最小的一条边若有两条或两条以上权一样且最小，则任取一条，在未选边中选一条权值最小的边

8、，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图T就是所求最小树。算法的详细步骤如下：第一步：令1=i，=0E空集第二步：选一条边iiEEe，且ie是使图),(1EEVGii?=-中不含圈的所有边)(iEEee中权最小的边。假如这样的边不存在，由v5v3图6.5),(1-=iEVT是最小树。第三步：把i换成1+i，返回第二步。例6.5用避圈法求图6.5的最小树。解：在,821eee中权值最小的边有51,ee，从中任取一条1e；在,832eee中选取权值最小的边5e；在,822eee中权值最小边有3e，7e，从中任取一条边3e；在,87642eee

9、ee中选取7e；在,8642eeee中选取84,ee。但4e与8e都会与已选边构成圈，故停止，得到与图6.6一样的结果。最小生成树minimalspanningtree,MST模型概括为：给定网络中一些点和这些点之间的距离，寻找连接所有这些点的最小总距离。使用LINGO软件编制此题的程序如下：MODEL:!Giventhenumberofnodesandthedistancebetweenthem,findingtheshortesttotaldistanceoflinksonthenetworktoconnectallthenodesistheclassicproblemcalledmini

10、malspanningtree(MST);SETS:CITY/1.5/:U;!U(I)=levelofcityI;!U(1)=0;3v5vv图6.6LINK(CITY,CITY):DIST,!Thedistancematrix;X;!X(I,J)=1ifweuselinkI,J;ENDSETSDATA:!Distancematrixneednotbesymmetric;!However,city1isbaseofthetree;!to:ABCDE;DIST=01346!fromA;10235!fromB;32013!fromC;43102!fromD;65320;!fromE;ENDDATA!

11、Themodelsize:Warning,maybeslowforN=8;N=SIZE(CITY);!Minimizetotaldistanceofthelinks;MIN=SUM(LINK:DIST*X);!ForcityK,exceptthebase,.;FOR(CITY(K)|K#GT#1:!Itmustbeentered;SUM(CITY(I)|I#NE#K:X(I,K)=1;!Ifthereare2disjointtoursfrom1citytoanother,wecanremovealinkwithoutbreakingconnections.Note:Thesearenotver

12、ypowerfulforlargeproblems;FOR(CITY(J)|J#GT#1#AND#J#NE#K:U(J)=U(K)+X(K,J)-(N-2)*(1-X(K,J)+(N-3)*X(J,K);););!Theremustbeanarcoutofcity1;SUM(CITY(J)|J#GT#1:X(1,J)=1;!MaketheXs0/1;FOR(LINK:BIN(X););!Thelevelofacityexceptthebaseisatleast1butnomorethanN-1,andis1ifitlinkstothebase;FOR(CITY(K)|K#GT#1:BND(1,

13、U(K),999999);U(K)END使用Solve求解获得如下结果：得到与图6.6一样的结果,X(1,2)=1,X(2,3)=1,X(3,4)=1,X(4,5)=1,其它X(I,J)=0。最优值6)(*=1122Tw。=+6.3最小生成树的应用与LINGO软件求解使用最小生成树程序应用求解下面详细例子。例6已知五个城市Atlanta,Chicago,Cincinnati,Houston和LA其距离矩阵如表6.1所示。求解连接五个城市网络的最小生成树。表6.1使用LINGO软件编制此题的程序如下：MODEL:!Giventhenumberofnodesandthedistancebetwee

14、nthem,findingtheshortesttotaldistanceoflinksonthenetworktoconnectallthenodesistheclassicproblemcalledminimalspanningtree(MST).Thismodelfindsthe(MST)connectingAtlanta,Chicago,Cincinnati,Houston,andLAsothatmessagescanbesentfromAtlanta(base)toothercitiesthroughthenetworkatminimumcost;SETS:CITY/1.5/:U;!

15、U(I)=levelofcityI;!U(1)=0;LINK(CITY,CITY):DIST,!Thedistancematrix;X;!X(I,J)=1ifweuselinkI,J;ENDSETSDATA:!Distancematrixneednotbesymmetric;!However,city1isbaseofthetree;!to:AtlChiCinHouLA;DIST=07024548422396!fromAtl;702032410932136!fromChi;454324011372180!fromCin;8421093113701616!fromHou;23962136218016160;!fromLA;ENDDATA!Themodelsize:Warning,maybeslowforN=8;