最小生成树

4．最小生成树及算法1v1)树(tree)的定义与树的特征定义连通且不含圈的无向图称为树．常用T表示.树中的边称为树枝.树中度为1的顶点称为树叶.孤立顶点称为平凡树.2v3v4v5v平凡树注意：无向图例如，图6.4.1给出的G1和G2是树，但G3（有圈）和G4（不连通）则不是树。G1G2G3G4图6.4.1定理2设G是具有n个顶点的图，则下述命题等价：1)G是树（G无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有n-1条边；4)G无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即G为最最小连通图）；6)G中任意两顶点间有唯一一条路.2）图的生成树(或支撑树SpanningTree)定义若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树.图G中不在生成树的边叫做弦.定理3图G=(V,E)有生成树的充要条件是图G是连通的.证明必要性是显然的.充分性：任取Vu1，令集合}{11uV，这时生成树T的边集)1(TE为空集.因为G是连通图，点集1V与1\VV之间必有边相连，设211uue为这样的边，1u属于1V而2u属于1\VV.则得},{212uuV，}{1)2(eET.重复进行上述步骤，对于},...,,{21iiuuuV，},...,,{121)(iiTeeeE，|)|(Vni，仍能找到边ie满足其一端在点集iV，另一端在点集iVV\中.由于ie有一端在iV之外，所以iV与)(iTE中的边不构成圈.当ni时，得到VuuuVnn},...,,{21，},...,,{121)(nnTeeeE，即图),()(nTEVT有1n条边且无圈，由定理2知，这是一棵树，且为图G的一棵生成树.一般来讲，一个图的生成树不唯一。例如，在图6.4.2中，(a)、(b)、(c)均是(d)的生成树。(c)(d)图6.4.2(a)(b)（II）找图中生成树的方法可分为两种：避圈法和破圈法A避圈法:深探法和广探法B破圈法A避圈法定理3的充分性的证明提供了一种构造图的生成树的方法.这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止.这种方法可称为“避圈法”或“加边法”在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.a)深探法若这样的边的另一端均已有标号，就退到标号为步骤如下：i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给以标号0.令i=0查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树图1001234567891011121313a)深探法图100123456789101112步骤如下：若这样的边的另一端均已有标号，就退到标号为i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给u以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树3b)广探法步骤如下：i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号.对所有未标号之点均标以i+1,记下这些iii)对标号i+1的点重复步步骤ii)，直到全部点得到给u以标号0.Vi,检查[Vi,V\Vi]中的边端点边.例用广探法求出下图10的一棵生成树图101012213212234标号为止.图103b)广探法步骤如下：i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号.对所有未标号之点均标以i+1,记下这些iii)对标号i+1的点重复步步骤ii)，直到全部点得到给u以标号0.令i=0.Vi,检查[Vi,V\Vi]中的边端点边.例用广探法求出下图10的一棵生成树图101012213212234标号为止.显然图10的生成树不唯一.B破圈法相对于避圈法，还有一种求生成树的方法叫做“破圈法”.这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止.例用破圈法求出取一圈}{1233211vevevev，去掉3e；取一圈}{123544211vevevevev，去掉5e；取一圈}{2657442vevevev，去掉7e；取一圈}{123856211vevevevev，去掉6e.下图的一棵生成树.B破圈法例用破圈法求出下图的另一棵生成树.取一圈}{123856211vevevevev,去掉8e；取一圈}{12354756211vevevevevev去掉6e；得到另一颗生成树.取一圈}{1233211vevevev,去掉3e；取一圈}{123544211vevevevev,去掉4e；不难发现，图的生成树不是唯一的.3)最小生成树(MinimumSpanningTree)与算法定义13设),(1EVT是赋权图),(EVG的一棵生成树，称T中全部边上的权数之和为生成树的权，记为)(Tw，即1)()(EeewTw.如果生成树*T的权)(*Tw是G的所有生成树的权中最小者，则称*T是G的最小生成树，简称为最小树，即)}({min)(*TwTwT，式中取遍G的所有生成树T.介绍最小生成树（MST）的三种算法：避圈法（Kruskal算法和Prim算法）和破圈法.AKruskal算法思路如下：1)选择边e1，使得w(e1)尽可能小；2)若已选定边，则从ieee,...,,21},...,,{\21ieeeE中选取，使得:1iei)为无圈图，}],...,,[{121ieeeGii)是满足i)的尽可能小的权，)(1iew3)当第2)步不能继续执行时，则停止.定理4由Kruskal算法构作的任何生成树}],...,,[{121*eeeGT都是最小树.Kruskal算法步骤(1)对属于E的边进行排序得12eee(2)初始化操作0,0,,0tkT（3）若t=n-1,则转（6），否则转（4）（4）若）转（构成一回路，则做4,1}{kkeTk）转（，3,1,1},{)5(kktteTTkk（6）输出T，w，停止},,,,,{876432eeeeee例10用Kruskal算法求下图的最小树.在左图中权值},...,,{821eee最小的边有任取一条,,51ee,1e在中选取权值},...,,{832eee,5e最小的边中权值最小边有,从中选：73,ee;3e任取一条边},,,,{87642eeeee会与已选边构成圈,故停止,得中选取在中选取,7e,,{42ee在中选取.但与都},86ee84,ee4e8e最小生成树的Prim算法•Prim算法思路–从任意一顶点开始，首先把这个顶点包括在生成树里，然后在那些其一端已在生成树里，而另一端还未在生成树里的边中，找权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树中。如此进行下去，每次往生成树里加入一个顶点和一条权最小的边，直到把所有顶点都包括进生成树里–理论上，当有两条具有相同最小权值的边可选择时，选哪一条都行，因此构造的最小生成树不一定唯一。但若给定算法，则唯一Prim算法的参考步骤第一步T0，w(T0)0，V{v0}。第二步对每一个点vVV，L(v)w(v,v0)（如果(v,v0)E，则w(v,v0)=）。第三步如果V=V，输出T0，w(T0)，停止。否则进行下一步。第四步在VV中找一点u，使L(u)=min{L(v)|vVV}，并将V中与u邻接的点记为x，e=(x,u)。第五步T0T0{e}，w(T0)w(T0)+w(e)，VV{u}。第六步对所有vVV，如w(v,u)L(v)，则L(v)w(v,u)，否则L(v)不变。第七步转第三步。步骤uL(b)L(c)L(d)L(e)L(f)L(g)eVT0C(T0)1a415728{a}02b－9728(a,b){a,b}{(a,b)}43e－532－28(a,e){a,b,e}{(a,b),(a,e)}114c－－25－28(c,e){a,b,e,c}{(a,b),(a,e),(c,e)}165d－－－－1612(c,d){a,b,e,c,d}{(a,b),(a,e),(c,e),(c,d)}416g－－－－16－(d,g){a,b,e,c,d,g}{(a,b),(a,e),(c,e),(c,d),(d,g)}537f－－－－－－(d,f){a,b,e,c,d,g,f}{(a,b),(a,e),(c,e),(c,d),(d,g),(d,f)}69从顶点a开始结果显示于图•最小生成树的Kruskal算法是1956年由Kruskal提出的。随后在1957年，领导贝尔实验室数学研究室的Prim创立了他的算法。Kruskal算法的时间复杂性以O(mlog2m)为界，当边数较多或是一个完全图时，m(n1)2，则时间复杂性近似于O(n2log2n)。而Prim算法的时间复杂性为O(n2)，所以，如果图的连通度较高（最高为完全图），以Prim算法较好，如果图的连通度较低，特别当mO(n)时，则Kruskal算法更合适。在实际应用中，还会遇到求一个赋权图的最大生成树的问题。比如，某图的边权代表的是利润或效益，则最终的问题很可能就是求其最大生成树。事实上，从上面两个算法可以看出，只要边权的选择改为从大到小，求最小生成树的算就可以用来求最大生成树了。令m表示边数B破圈法算法2步骤如下：1)从图G中任选一棵树T1.2)加上一条弦e1，T1+e1中立即生成一个圈.去掉此圈中最大权边，得到新树T2,以T2代T1,重复2)再检查剩余的弦，直到全部弦检查完毕为止.例11用破圈法求下图的最小树.先求出上图的一棵生成树.加以弦e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新树仍是原来的树；2e再加上弦e7，得到圈v4v5v2v4,27e去掉最大的权边e6，得到一棵新树；如此重复进行，直到全全部的弦均已试过,得最小树.应用—连线问题•欲修筑连接个城市的铁路，已知城与城之间的铁路造价为，设计一个线路图，使总造价最低。•连线问题的数学模型是在连通赋权图上求权最小的生成树。分组技术。分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工都在组内完成。假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。将这9台机器分为3组，使零件跨组加工的情形尽量少。机器123456789加工的零件2，3，7，8，9，12，132，7，8，11，121，63，5，103，7，8，9，12，1354，104，106应用范例解：(1)建模设用Mi表示需由机器i加工的零件集合。对任意两台机器i，j，定义i与j的相异度：其中“”表示对称差，分子即为在机器i但不在机器j上加工，或在机器j但不在机器i上加工的零件数。分母为在机器i或在机器j上加工的零件数。显然，0w1，w(i,j)=0表示机器i与机器j加工的零件完全相同；w(i,j)=1表示机器i与机器j加工的零件没有一个相同。w表达了两台不同机器加工零件的相异程度。||||),(jijiMMMMjiw以机器为顶点，作一个完全图，每条边(i,j)被赋予权w(i,j)。这个图的最小生成树是由那些相异度最小的边构成的连通图，或看成是去掉了相异度相对比较大的边后余下的连通图。如果希望把机器分成k个组，就继续删去最小生成树上权最大的k1条边。于是得到k个分离的子树，每棵树的顶点就构成各机器组。(2)模型求解对前面表中给出的数据，按照上述建模方式构造加权图，边权矩阵如下表所示。边111111112222234567893456边权0.510