(8.2.1)--08_2树及最小树问题.pdf

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中属于支撑树的边称为树枝，不在支撑树中的边称为弦。由以上充分性的证明中，提供了一个寻求连通图的支撑树的方法,称这种方法为“破圈法”。定理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的一个支撑子图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如果图是赋权图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步。避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。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，这时，任一未选边的边都与已选边构成圈，算法终止。，这时，任一未选边的边都与已选边构成圈，算法终止。