浅析树形图的连通性及其求解方法.doc

肅芃芅袂羁节莇蚅袇芁薀袀袃芀蚂螃膂艿莂薆肈芈蒄螁羄芇薆薄袀芇芆螀螆莆莈薂肄莅蒁螈羀莄蚃薁羆莃莃袆袂莂蒅虿膁莁薇袄肇莁蚀蚇羃莀荿袃衿肆蒁蚆螅肅薄袁肃肄芃蚄聿肄蒆罿羅肃薈螂袁肂蚀薅膀肁莀螀肆肀蒂薃羂腿薅蝿袈腿芄薂螄膈莇螇膂膇蕿蚀肈膆蚁袅羄膅莁蚈袀膄蒃袄螆膃薅蚆肅芃芅袂羁节莇蚅袇芁薀袀袃芀蚂螃膂艿莂薆肈芈蒄螁羄芇薆薄袀芇芆螀螆莆莈薂肄莅蒁螈羀莄蚃薁羆莃莃袆袂莂蒅虿膁莁薇袄肇莁蚀蚇羃莀荿袃衿肆蒁蚆螅肅薄袁肃肄芃蚄聿肄蒆罿羅肃薈螂袁肂蚀薅膀肁莀螀肆肀蒂薃羂腿薅蝿袈腿芄薂螄膈莇螇膂膇蕿蚀肈膆蚁袅羄膅莁蚈袀膄蒃袄螆膃薅蚆肅芃芅袂羁节莇蚅袇芁薀袀袃芀蚂螃膂艿莂薆肈芈蒄螁羄芇薆薄袀芇芆螀螆莆莈薂肄莅蒁螈羀莄蚃薁羆莃莃袆袂莂蒅虿膁莁薇袄肇莁蚀蚇羃莀荿袃衿肆蒁蚆螅肅薄袁肃肄芃蚄聿肄蒆罿羅肃薈螂袁肂蚀薅膀肁莀螀肆肀蒂薃羂腿薅蝿袈腿芄薂螄膈莇螇膂膇蕿蚀肈膆蚁袅羄膅莁蚈袀膄蒃袄螆膃薅蚆肅芃芅袂羁节莇蚅袇芁薀袀袃芀蚂螃膂艿莂薆肈芈蒄螁羄芇薆薄袀芇芆螀螆莆莈 浅析树形图的连通性及其求解方法董利娟06200101信计061班摘要 本文在有向图中引入了树形图的概念，并证明了树形图的连通性，在此基础上结合广探法和深探法思想，给出了求全部树形图的广探算法，而且指出树形图不具有Hamilton性。关键词 有向树，树形图背景 在无向图中我们往往考虑无向图中树的性质及最有生成树算法，那么在有向图中就要讨论有向树及树形图，它们在计算机算法、计算机程序中有着重要的作用。此外，有向树常用来描述带有“带有”体系性质的结构，如图书馆的书籍分类等。正文 文献23提出了求全部树形图的深探算法。45研究了最小树图的边Hanmilton性。并给出了求全部最小树的广探算法。有关图论术语及符号见文献1和文献6。 定义1一个有向图D，如果略去每条弧的方向时所得到无向图是一颗树，就称D为有向树。定义2设G=（V,A）是有向图，其中V是其顶点集合，A 是其弧集合。T(G)表示根在顶点r的G的全部有向树（以下简称G的全部树形图）集合。设,称是相邻的，如果G中存在两弧，使得（亦称此运算为一一交换）。以T(G)为顶点集合，以相邻关系的边可以构成一无向图，仍记为T(G)，称T(G)为G的树形图。1 两个定理定理1 有向图G的树形图T(G)是连通的。证：对任意，只要证明在T(G)上存在到的路即可，即通过若干一一交换可由得到。为此，将上所有弧铵根r到其末点的距离分层，距离为i者属第i层，然后逐层检查，各层上弧是否相同。若第一层上有不同弧，因上r到有唯一有向路，设为（r,r）构成上的唯一圈，而一一交换后，是树形图，且比的相同弧多了一条。假设，上的第1，2，k-1层上对应弧相同，第k层上有一条不同弧，因上r到有唯一有向路（r,，），显然（r,，）是+上的唯一圈，那么一一交换后，+-是树形图，且与的相同弧增加了一条。因有限，故有限次一一交换可以由变到，即T(G)是连通的。证毕。定义3设u是树形图T的任一顶点，以u为根，u及其所有子孙所组成的顶点集记,u到这些子孙的有向路上所有弧组成的弧集记为,称T的子图为以u为根的子树。定义4设=（，）是G的一颗树形图（其中n=）是G的顶点数），此处各弧编号是从树梢编起，使在上不存在的终点到（ij）的始点的有向路。 对的任一弧子集,，（1kn-1）()，记（）=TT(G): =,，是包含，且不含中元素的树形图全体。 设=（），-将分为两个有向子树，顶点集分别为，且r，定义 那么包含-，且不包含的树形图全体 T(i)= + a - :a一般的，我们有定理2 T（） = T + a -:a ,TT()且不出现重复枚举。证：显然等式左边右边，下面证左边右边，即对任意 T（）使=T+a-,a。因，设上与终点相同的弧是a,我们说+-a是树形图。否则+-a中存在包含的有向圈，那么上存在包含a的由根r到的始点的唯一有向路，而上存在不包含由根r到的始点的唯一有向路，设为,所以必有,而=,，,设=（jk）,那么的终点到的始点存在有向路，这与中弧的编号矛盾。所以+-a是树形图。令T = + - a,则T T(), = T + a -,a。对任意（）（），由定义知T（）T()=,即此处所给递推公式中不出现重复枚举，亦即T(G)= T（）是不交并。证毕。2 算法 有了定理2，我们就可以设计产生全部树形图的算法，此算法结合了广探法和深探法思想，用广探法产生每个集合T（），而由T（）递归生成T（）的这种运行思想是基于深探法。 产生全部树形图的广探算法：第0步：k=1, =1, =；第2步：求T()=T+a-:a,T;第3步：若2,则令 = T()， = +1， k = k - 1,转到第2步；（2）若k=2,则令 = ， = + 1 k = k- 1,转到第2步；（3）若k=1,则算法停止。定理3 产生全部树形图的算法是正确的，其所需时间为0（mk）,其中m=为G的弧数，k为集合T()的个数，k = 2n-1 。证：算法由开始，产生所有 T()，结束于T(n-1),由定理2知算法找到了所有树形图T(G)。 对任意树形图T的弧a,求割集的时间不超过0（K）。证毕。2 例子与说明例子 考虑如下图G，r为根。 =，；T(1)= ;T(1,2)= ,;T(1,2,3)= ,T(1,3)= ;所以T(G)= T(1)T(2)T(1,2,3)T(2,3)为G的根在r的树形图的全体。说明：1. 无向图中树形图的边Hamilton性34在有向图图上并不成立。如下图G，容易验证树形图在T(G)中的次数为1.所以T(G)中不存在Hamilton圈，而G的顶点数可以任意大。2. 由定理2知，若T（）= ，则T（）。故非空集合T（）的个数2n-13)。从而此算法比已有的算法有效。总结 树形图概念非常重要，原因在于它描述了一个离散结构的层次关系，而层次结构是一种重要的数据结构，所以树形结构在相当广泛的领域中有它的应用。 首先要明确树形图是连通图。 其次学会在实例中用广探算法来求有向图的全部树形图。 另外树形图不具有Hamilton性也是一个重要的性质。参考文献1 卜月华.图论及其应用.2000，32 Gabow H W,Myers E W.Finding all spanning trees of a directed and undirectrd graph.SLAM J Comput.1978,7:2802873 房大中.生成有向图全部有向树的新算法.天津大学学报.1990，1：931014 林治勋，张福基.最小树图的Hamilton性全部最小树的生成.数学年刊，1985，6（6）：7157185 林治勋. 最小树问题的全部解，数学的实矩与认识，1985，2：42476 Bondy,V S R Murty.Graph Theory with applications.The Macmillan press:LTB,19767 AHO A V ,J E Hopcroft,J D man.The Design and Analysis of Computer Algorithms.Reading,Mass:Addison-Wesley,19768 刘瑞金，侯文华，翁莉娟.有向树图的连通性及其算法.北京轻工业学院学报，1995，6：第13卷第1期 莁袃肄艿薇蝿肃莂荿蚅肂肁薅薁膁膄莈袀膀芆薃螆腿蒈莆螁膈膈蚁蚇螅芀蒄薃螄莃蚀袂螃肂蒃螈螂膄蚈蚄袂芇蒁薀袁荿芄衿袀聿葿袅衿芁节螁袈莃薇蚇袇肃莀薃袆膅薆袁袆芈荿螇羅莀薄蚃羄肀莇蕿羃膂薂薅羂莄蒅袄羁肄蚁螀羀膆蒃蚆羀艿虿薂罿莁蒂袀肈肀芅螆肇膃蒀蚂肆莅芃蚈肅肅薈薄肄膇莁袃肄艿薇蝿肃莂荿蚅肂肁薅薁膁膄莈袀膀芆薃螆腿蒈莆螁膈膈蚁蚇螅芀蒄薃螄莃蚀袂螃肂蒃螈螂膄蚈蚄袂芇蒁薀袁荿芄衿袀聿葿袅衿芁节螁袈莃薇蚇袇肃莀薃袆膅薆袁袆芈荿螇羅莀薄蚃羄肀莇蕿羃膂薂薅羂莄蒅袄羁肄蚁螀羀膆蒃蚆羀艿虿薂罿莁蒂袀肈肀芅螆肇膃蒀蚂肆