最小生成树模型与实验

最优化模型与实验第155页第六章最小生成树模型与实验树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。§6.1树与树的性质上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。例6.1已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。用五个点54321,,,,vvvvv代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。定义6.1一个无圈的连通图称为树.例6.2某大学的组织机构如下所示:1v1v2v5v3v4v图6.1第六章最小生成树模型与实验第页156教务处研究处校行政办公室研究生院财务科行政科理工学院人事学院外语学院……如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。树的性质：（1）树必连通，但无回路（圈）；（2）n个顶点的树必有1n条边；（3）树中任意两点间，恰有一条初等链；（4）树连通，但去掉任一条边，必变为不连通；（5）树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。生成树与最小树定义6.2设图),(11EVG是图},{EVG的生成子图，如果1G是一棵树，记),(1EVT，则称T是G的一棵生成树。定理6.1图G有生成树的充分必要条件是图G的连通的。证：必要性是显然的充分性：设G是连通图。（i）如果G不含圈，由定义6.1可知，G本身就是一棵树，从而G是它自身的生成树。（ii）如果G含圈，任取一圈，从圈中任意去掉一条边，得到图G的数学系物理系文科办公室理科办公室校教学办公室校长最优化模型与实验第157页一个生成子图1G，如果1G不含圈，那么1G是G的一棵生成树（因为易见1G是连通的）；如果1G仍含少量圈，那么从1G中任取一个圈，从圈中再任意去掉一条边，得到图G的一个生成子图2G，如此重复，最终可以得到G的一个生成子图kG，它不含圈，则kG是图G的一棵生成树。§6.2最小生成树的实例与求解由以上充分性的证明中，提供了一个寻求连通图的生成树的方法，称这种方法为“破圈法”。例6.4在图6.1中，用破圈法求出图的一棵生成树解：取一圈}{1233211vevevev去掉3e；取一圈}{123544211vevevevev去掉5e；取一圈}{2657442vevevev去掉7e；取一圈}{123856211vevevevev去掉6e；如图6.3所示，此图是图6.2的一个生成子图，且为一棵树（无圈），所以我们找一棵生成树},{11EVT，其中，},,,{82411eeeeE。不难发现，图的生成树不是唯一的，对于上例若这样做：取一圈}{1233211vevevev去掉3e；取一圈}{123554211vevevevev去掉4e；取一圈}{123856211vevevevev去掉6e；取一圈}{4538574vevevev去掉8e。4v8e4e2e1e15e6e1v1v5v3v2v图6.23ee7第六章最小生成树模型与实验第页158图6.3图6.4如图G的生成树还有另外一种方法“避圈法”，主要步骤是在图中任取一条边1e，找出一条不与1e构成圈的边2e，再找出不与},{21ee构成圈的边3e。一般地，设已有},,,{21keee，找出一条不与},,,{21keee构成圈的边1ke，重复这个过程，直到不能进行下去为止。这时，由所有取出的边所构成的图是图G的一棵生成树。定义6.2设},{EVT是赋权图},{EVG的一棵生成树，称E中全部边上的权数之和为生成树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是一赋权图。最优化模型与实验第159页],[211vve，1)(1ew；],[312vve，4)(2ew；],[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中，任取权值最小的一条边（若有两条或两条以上权相同且最小，则任取一条），在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图T就是所求最小树。算法的具体步骤如下：第一步：令1i，0E（空集）第二步：选一条边iiEEe\，且ie是使图}){,(1EEVGii中不含圈的所有边)\(iEEee中权最小的边。如果这样的边不存在，由),(1iEVT是最小树。第三步：把i换成1i，返回第二步。例6.5用避圈法求图6.5的最小树。11v1v5v3v2v4v3512423图6.5第六章最小生成树模型与实验第页160解：在},,,{821eee中权值最小的边有51,ee，从中任取一条1e；在},,,{832eee中选取权值最小的边5e；在},,,{822eee中权值最小边有3e，7e，从中任取一条边3e；在},,,,{87642eeeee中选取7e；在},,,{8642eeee中选取84,ee。但4e与8e都会与已选边构成圈，故停止，得到与图6.6一样的结果。最小生成树（minimalspanningtree,MST）模型概括为：给定网络中一些点和这些点之间的距离，寻找连接所有这些点的最小总距离。使用LINGO软件编制此题的程序如下：MODEL:!Giventhenumberofnodesandthedistancebetweenthem,findingtheshortesttotaldistanceoflinksonthenetworktoconnectallthenodesistheclassicproblemcalledminimalspanningtree(MST);SETS:CITY/1..5/:U;!U(I)=levelofcityI;!U(1)=0;LINK(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;2v23v4v5v1v112图6.6最优化模型与实验第161页ENDDATA!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:Thesearenotverypowerfulforlargeproblems;@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;!MaketheX's0/1;@FOR(LINK:@BIN(X););!Thelevelofacityexceptthebaseisatleast1butnomorethanN-1,andis1ifitlinkstothebase;@FOR(CITY(K)|K#GT#1:@BND(1,U(K),999999);U(K)=N-1-(N-2)*X(1,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。最优值62121)(*Tw。第六章最小生成树模型与实验第页162§6.3最小生成树的应用与LINGO软件求解使用最小生成树程序应用求解下面具体例子。例6已知五个城市Atlanta,Chicago,Cincinnati,Houston和LA其距离矩阵如表6.1所示。求解连接五个城市网络的最小生成树。表6.1距离ikmjATLCHICINHOULAATL07024548422396CHI702032410932136CIN454324011372180HOU8421093113701616LA23962136210816160使用LINGO软件编制此题的程序如下：MODEL:!Giventhenumberofnodesandthedistancebetweenthem,findingtheshortesttotaldistanceoflinksonthenetworktoconnectallthenodesistheclassicproblemcalledminimalspanningtree(MST).Thismodelfindsthe(MST)connectingAtlanta,Chicago,Cincinnati,Houston,andLAsothatmessagescanbesentfromAtlanta(base)toothercitiesthroughthenetworkatminimumcost;SETS:CITY/1..5/:U;!U(I)=levelofcityI;!U(1)=0;LINK(CITY,CITY):DIST,!Thedistancematrix;X;!X(I,J)=1ifweuselinkI,J;ENDSETSDATA:!Distancematrixneednotbesymmetric;!However,city1isbaseofthetree;!to:AtlChiCinHouLA;最优化模型与实验第163页DIST=07024548422396!fromAtl;702032410932136!fromChi;454324011372180!fromCin;8421093113701616!fromHou;23962136218016