《(8.2.1)--08_2树及最小树问题.pdf》由会员分享,可在线阅读,更多相关《(8.2.1)--08_2树及最小树问题.pdf(11页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、v1v2v3v4v5v6一个连通的无圈的连通图叫做树。树中次为1的点称为树叶,次大于1的点称为分支点。树及最小树问题1 树及其性质树的性质定理3 设图G=(V,E)是一个树,p(G)2,则G中至少有两个悬挂点。定理4 图G=(V,E)是一个树的充分必要条件是G不含圈,且恰有p1条边。定理5 图G=(V,E)是一个树的充分必要条件是G是连通图,并且q(G)=p(G)1定理6 图G是树的充分必要条件是任意两个顶点之间恰有一条链。v1v2v3v4v5v1v2v3v4v5支撑树设图是图G=(V,E)的一支撑子图,如果图是一个树,那么称K 是G 的一个支撑树(生成树),或简称为图G 的树。图G中属于支撑
2、树的边称为树枝,不在支撑树中的边称为弦。由以上充分性的证明中,提供了一个寻求连通图的支撑树的方法,称这种方法为“破圈法”。定理7 一个图G 有支撑树的充要条件是G 是连通图。求连通图的支撑树的方法有“破圈法”和“避圈法”。证:必要性是显然的。充分性:设G是连通图。(i)如果G不含圈,由定义可知,G本身就是一个树,从而G是它自身的支撑树。(ii)如果G含圈,任取一圈,从圈中任意去掉一条边,得到图G的一个支撑子图G G1 1。如果G G1 1不含圈,那么G G1 1是G的一棵支撑树(因为易见G G1 1是连通的);如果G1仍含圈,那么从G G1 1中任取一个圈,从圈中再任意去掉一条边,得到图G的一
3、个支撑子图G G2 2,如此重复,最终可以得到G的一个支撑子图G Gk k,它不含圈,则G Gk k是图G的一棵支撑树。(一)破圈法(二)避圈法在图中任取一条边e1,找一条与e1不构成圈的边e2,再找一条与e1,e2不构成圈的边e3。一般设已有e1,e2,ek,找一条与e1,e2,ek中任何一些边不构成圈的边ek+1,重复这个过程,直到不能进行为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5某六个城市之间的道路网如图 所示,要求沿着已知长度的道路联结六个城市的电话线网,使电话线的总长度最短。v1v2v3v4v5v6655723441
4、如果图是赋权图G的一个支撑树,那么称E1上所有边的权的和为支撑树T的权,记作S(T)。如果图G的支撑树T*的权S(T*),在G 的所有支撑树T中的权最小,即那么称T*是G 的最小支撑树。3 最小支撑树问题v1v2v3v4v5v6651572344破圈法:任选一个圈,从圈中去掉权最大的一条边。在余下的图中重复这个步骤,直到得到一不含圈的图为止。算法的具体步骤如下:第1步:令i=1,E0=(空集)。第2步:选一条边eiEEi-1,且e是使图Gi=(V,Ei-1e)中不含圈的所有边中权最小的边e(eEEi)。如果这样的边不存在,则T=(V,Ei-1)是最小树。第3步:把i换成i+1,返回第2步。避圈
5、法:开始选一条权最小的边,以后每一步中,总从未被选取的边中选一条权尽可能小,且与已选边不构成圈的边。v6v3v2v16551 72344v4v5v3v21v42v53v64v15i=1=1,E0=,=,从从E E中选最小边中选最小边 v2,v3,E1=v2,v3。i=2,=2,从从E E E E1 1中选最小边中选最小边 v2,v4,(v2,v4 与与 v2,v3 不构成圈不构成圈),),E2=v2,v3,v2,v4。i=3=3,从,从E E E E2 2中选最小边中选最小边 v4,v5,(V,E2v4,v5 不含圈不含圈),),E3=v2,v3,v2,v4,v4,v5。i=4=4,从,从E E E E3 3中选最小边中选最小边 v5,v6,(V,E3v5,v6 不含圈不含圈),),E4=v2,v3,v2,v4,v4,v5,v5,v6。i=5=5,从,从E E E E4 4中选最小边中选最小边 v1,v2,(V,E4v1,v2 不含圈不含圈),),E5=v2,v3,v2,v4,v4,v5,v5,v6,v1,v2。i=6=6,这时,任一未选边的边都与已选边构成圈,算法终止。,这时,任一未选边的边都与已选边构成圈,算法终止。
限制150内