浅析树形图连通性其求解方法

1、浅析树形图的连通性及其求解方法浅析树形图的连通性及其求解方法PAGEPAGE5浅析树形图的连通性及其求解方法PAGE浅析树形图的连通性及其求解方式董利娟06200101信计061班纲领本文在有向图中引入了树形图的见解，并证了然树形图的连通性，在此基础上结合广探法和深探法思想，给出了求所有树形图的广探算法，而且指出树形图不拥有Hamilton性。重点词有向树，树形图背景在无向图中我们常常考虑无向图中树的性质及最有生成树算法，那么在有向图中就要谈论有向树及树形图，它们在计算机算法、计算机次澄彻中有重视要的功能。其余，有向树常常使用来描绘带有“带有”系统性质的结构，如书本室的书本分类等。本文文件23

2、提出了求所有树形图的深探算法。45研究了最小树图的边Hanmilton性。并给出了求所有最小树的广探算法。相关图论术语及符号见文件1和文件6。界说1一个有向图D，若是略去每条弧的目标时所获得无向图是一颗树，就称D为有向树。界说2设G=（V,A）是有向图，其中V是其极点靠拢，A是其弧靠拢。T(G)表示根在极点r的G的所有有向树（以下简称G的所有树形图）靠拢。设T1,T2T(G),称T1,T2是相邻的，如果G中存在两弧aT2,bT1，使得T1ab极点靠拢，以相邻关系的边能够组成一无向图，仍记为T2（亦称此运算为一一交换）。以T(G)为T(G)，称T(G)为G的树形图。两个定理定理1有向图G的树形图

3、T(G)是连通的。证：对任意T1,T2T(G)，只要证明在T(G)上存在T1到T2的路即可，即经过几何一一交换可由T1获得T2。为此，将第i层，今后逐层查验T1T2上所有弧铵根r到其末点的间隔分层，间隔为i者属，T2各层上弧可否相同。若第一层上有不一样样弧r,v1T2,r,v1T1，因T1上r到v1有唯一有向路，设为（r,v,v1,r）组成T1r,v1上的唯一圈，而一一交换后，T1r,v1(v,v1)是树形图，且比T2的相同弧多了一条。假设T1，T2上的第1，2，,，k-1层上对应弧相同，第k层上有一条不一样样弧(Vk1,Vk)T2,(Vk1,Vk)T1，因T1上r到Vk有唯一有向路（r,，v

4、，Vk），显然v,VkT2,（r,，v，Vk，Vk1）是T1+(Vk1,Vk)上的唯一圈，那么一一交换后，T1+(Vk1,Vk)-v,Vk是树形图，且与T2的相同弧增添了一条。因T2T1有限，故有限次一一交换能够由T1变到T2，即T(G)是连通的。证毕。界说3设u是树形图T的任一极点，以u为根，u及其所有后辈所组成的极点集记V,u到这些后辈的有向路上所有弧组成的弧集记为E,称T的子图T(V,E)为以u为根的子树。界说4设T0=（a1，,，an1）是G的一颗树形图（其中n=V）是G的极点数），此处各弧编号是从树梢编起，使在T0上不存在ai的终点到aj（ij）的始点的有向路。对T的任一弧子集Aa,

5、，a（1kn-1）(i,i)，记（i,ik）=TT(G):0kiik1k1T0T=ai,，aik是包含T0Ak，且不含Ak中元素的树形图所有。设ai=（V1,V2），T0-ai将T0分为两个有向子树，极点集辩白为V1,V2，且r，v1V1，界说DT0(ai)(v1,v2)G:VV1v1那么包含T0-ai，且不包含ai的树形图所有T(i)=T0+a-aDT0(a)i:ai正常的，我们有定理2T（i1,ik）=T+a-aDT0(aik),TT(i1,ik1)且不出现重ik:a复排列。证：显然等式左边右边，下面证左边右边，即对任意TT（i1,ik）使T=T+a-aik,aDT(aik)。因aikT，

6、设T上与aik终点相同的弧是a,我们说T+aik-a是树形图。否则T+aik-a中存在包含aik的有向圈，那么T上存在包含a的由根r到aik的始点的唯一有向路，而T0上存在不包含由根r到aik的始点的唯一有向路，设为P0,所以必有aT0T,aP0,而T0T=ai,，aik,设a=aij（jk）,那么aij的终点到aik的始点存在有向路，这与T0中弧的编号矛盾。所以T+aT=T+aik-a是树形图。令ik-a,则TT(i1,ik1),T=T+a-aik,aDT(aik)。对任意（i1,ik）（j1,jl），由界说知T（i1,ik）T(j1,jl)=,即此处所给递推公式中不出现频频排列，亦即T(G

7、)=T0T（i1,ik）是不交并。证毕。算法有了定理2，我们就能够够策划发生所有树形图的算法，此算法结合了广探法和深探法思想，用广探法发生每一个靠拢T（i1,ik），而由T（i1,ik1）递归生成T（i1,ik）的这种运行思想是基于深探法。发生所有树形图的广探算法：第0步：k=1,ik=1,k1=T0；第2步：求T(i1i2,ik)=T+a-aik:aDT(aik),Tk1;第3步：若ik2,则令k2=T(i1,ik2)，ik1=ik1+1，k=k-1,转到第2步；（2）若k=2,则令k2=T0，ik1=ik1+1k=k-1,转到第2步；（3）若k=1,则算法暂停。定理3发生所有树形图的算法是

8、正确的，其所需时间为0（mk）,其中m=A为G的弧数，k为靠拢T(i1,ik)的个数，k=2n-1。证：算法由T0开始，发生所有有树形图T(G)。T(i1,ik)，完成于T(n-1),由定理2知算法找到了所对任意树形图T的弧a,求割集DT(a)的时间不高出0（AK）。证毕。例子与说明例子考虑以以以下列图G，r为根。T0=a1，a2,a3；T(1)=a6,a2,a3;T(1,2)=a,a4,a,a,aa;6345,3T(1,2,3)=a6,a4,a2,a6,a4,a1,a6,a5,a2,a6,a5,a1T(1,3)=;所以T(G)=T0T(1)T(2)T(1,2,3)T(2,3)为G的根在r的树

9、形图的所有。说明：1.无向图中树形图的边Hamilton性34在有向图图上其实不成立。以以以下列图G，简单考据树形图T0在T(G)中的次数为1.所以T(G)中不存在Hamilton圈，而G的顶点数能够任意大。2.由定理2知，若T（i1,ik1）=，则T（i1,ik）。故非空靠拢T（i1,ik）的个数2n-13)。进而此算法比已有的算法合用。总结树形图见解特别重要，原因在于它描绘了一个失散结构的品位关系，而品位结构是一种重要的数据结构，所以树形结构在相当遍及的范围中有它的运用。开始要鲜亮树形图是连通图。其次学会在实例中用广探算法来求有向图的所有树形图。其余树形图不拥有Hamilton性也是一个重

10、要的性质。参照文件卜月华.图论及其运用.2000，32GabowHW,MyersEW.Findingallspanningtreesofadirectedandundirectrdgraph.SLAMJComput.1978,7:2802873房大中.生成有向图所有有向树的新算法.天津大学学报.1990，1：93101林治勋，张福基.最小树图的Hamilton性所有最小树的生成.数学年刊，1985，6（6）：7157185林治勋.最小树问题的所有解，数学的实矩与认识，1985，2：42476Bondy,VSRMurty.GraphTheorywithapplications.TheMacmillanp