图论课件最小生成树

0.810.60.40.20xt00.511.5210.500.51n1本次课主要内容最小生成树(一)、克鲁斯克尔算法(二)、管梅谷的破圈法(三)、Prim算法(四)、计算机中的树简介0.810.60.40.20xt00.511.5210.500.51n2最小连接问题：交通网络中，常常关注能把所有站点连接起来的生成树，使得该生成树各边权值之和为最小。例如：假设要在某地建造5个工厂，拟修筑道路连接这5处。经勘探，其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上，如果我们要求铺设的道路总长度最短，这样既能节省费用，又能缩短工期，如何铺设？v1v2v3v4v5122434550.810.60.40.20xt00.511.5210.500.51n3v1v2v3v4v51223不难发现：最小代价的连接方式为：最小连接问题的一般提法为：在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。(一)、克鲁斯克尔算法0.810.60.40.20xt00.511.5210.500.51n4克鲁斯克尔(Kruskal):1928年生，一家3弟兄都是数学家，1954年在普林斯顿大学获博士学位，导师是ErdÖs,他大部分研究工作是数学和语言学，主要在贝尔实验室工作。1956年发表包含克鲁斯克尔算法论文，使他名声大振。1、算法思想从G中的最小边开始，进行避圈式扩张。2、算法(1)、选择边e1,使得其权值最小；(2)、若已经选定边e1,e2,…,ek,则从E-｛e1,e2,…,ek｝中选择边ek+1,使得：(a)、G[e1,e2,…,ek+1]为无圈图(b)、ek+1的权值w(ek+1)尽可能小。0.810.60.40.20xt00.511.5210.500.51n5(3)、当(2)不能进行时，停止。例1用克鲁斯克尔算法求下图的最小生成树。3v721546789101112v1v2v3v4v5v6v80.810.60.40.20xt00.511.5210.500.51n6解：过程如下：1v5v821v1v5v8321v1v4v5v83v7215v1v4v5v83v72156v1v4v5v8v30.810.60.40.20xt00.511.5210.500.51n73v72156v1v4v5v8v3v683v72156v1v4v5v8v3v68v292、算法证明定理1由克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明：设G是一个n阶连通赋权图，用T*=G[｛e1,e2,…,en-1｝]表示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小生成树。0.810.60.40.20xt00.511.5210.500.51n8设T是G的一棵最小生成树。若T*≠T由克鲁斯克尔算法容易知道：T∩T*≠Φ。于是令f(T)=k表示T*中的边ei不在T中的最小i值。即可令T=G[｛e1,e2,…,ek-1,e'k,…,e'n｝]考虑：T∪ek,则由树的性质，它必然为G中圈。作T1=T∪ek-e,容易知道：T1还为G的一棵生成树。设e是圈T∪ek中在T中，但不在T*中的边。由克鲁斯克尔算法知道：()()kwewe所以：1()()wTwT这说明T1是最小树，但这与f(T)的选取假设矛盾！所以：T=T*.0.810.60.40.20xt00.511.5210.500.51n9例2在一个边赋权G中，下面算法是否可以产生有最小权值的生成路？为什么？算法:(1)选一条边e1,使得w(e1)尽可能小；(2)若边e1,e2,…,ei已经选定，则用下述方法从E\｛e1,..,ei｝中选取边ei+1：(a)G[｛e1,e2,…,ei,ei+1｝]为不相交路之并；(b)w(ei+1)是满足(a)的尽可能小的权。(3)当(2)不能继续执行时停止。解：该方法不能得到一条最小生成路。0.810.60.40.20xt00.511.5210.500.51n10例如，在下图G中我们用算法求生成路：3122343667910用算法求出的生成路为：1226930.810.60.40.20xt00.511.5210.500.51n11直接在图中选出的一条生成路为：123366后者的权值小于前者。(二)、管梅谷的破圈法在克鲁斯克尔算法基础上，我国著名数学家管梅谷教授于1975年提出了最小生成树的破圈法。0.810.60.40.20xt00.511.5210.500.51n12管梅谷（１９３４－）。我国著名数学家，曾任山东师范大学校长。中国运筹学会第一、二届常务理事，第六届全国政协委员。从事运筹学及其应用的研究，对最短投递路线问题的研究取得成果，冠名为中国邮路问题，该问题被列入经典图论教材和著作。管梅谷教授1957年至1990年在山东师范大学工作。1984年至1990年担任山东师范大学校长，1990年至1995年任复旦大学运筹学系主任。1995年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员，国际项目办公室高级顾问及复旦大学管理学院兼职教授。自1986年以来，管教授致力于城市交通规划的研究，在我国最早引进加拿大的交通规划EMMEⅡ软件，取得一系列重要研究成果。0.810.60.40.20xt00.511.5210.500.51n13破圈法求最小生成树的求解过程是：从赋权图G的任意圈开始，去掉该圈中权值最大的一条边，称为破圈。不断破圈，直到G中没有圈为止，最后剩下的G的子图为G的最小生成树。证明可以参看《数学的认识与实践》4，(1975),38-41。3122343667910例3用破圈法求下图G的最小生成树。0.810.60.40.20xt00.511.5210.500.51n14312234366710解：过程如下：31223466710312236671031226671031226673122660.810.60.40.20xt00.511.5210.500.51n15(三)、Prim算法Prim算法是由Prim在1957年提出的一个著名算法。作者因此而出名。Prim(1921---)1949年在普林斯顿大学获博士学位，是Sandia公司副总裁。Prim算法：对于连通赋权图G的任意一个顶点u，选择与点u关联的且权值最小的边作为最小生成树的第一条边e1;在接下来的边e2,e3,…,en-1,在于一条已经选取的边只有一个公共端点的的所有边中，选取权值最小的边。用反证法可以证明该算法。即证明：由Prim算法得到的生成树是最小生成树。(证明略)0.810.60.40.20xt00.511.5210.500.51n16例4用Prim算法求下图的最小生成树。554432176v1v2v3v4v5解：过程如下：1v1v231v1v2v30.810.60.40.20xt00.511.5210.500.51n17431v1v2v3v44321v1v2v3v4v5最小生成树权值为：w(T)=10.例5连通图G的树图是指这样的图，它的顶点是G的生成树T1,T2,…,Tτ,Ti与Tj相连，当且仅当它们恰有n-2条公共边。证明任何连通图的树图是连通图。证明：只需证明,对任意Ti与Tj，在树图中存在连接它们的路即可！0.810.60.40.20xt00.511.5210.500.51n18对任意Ti与Tj,设｛e1,e2,…,ek｝(kn-2)是它们的公共边。由树的性质：11(),()kikjeETeET但使得：。该圈中：1jkTe有唯一圈11(),()kjkieETeET但作：111iikkTTee则Ti与Ti+1有n-2条边相同，于是，它们邻接。此时，Ti+1与Tj有k+1条边相同。如此这样作下去，可以得到连接Ti与Tj的一条路为：1,,,iijTTT所以，连通图G的树图是连通的。0.810.60.40.20xt00.511.5210.500.51n19(四)、计算机中的树简介在计算机科学中，常常遇到所谓的根树。定义2：一棵树T，如果每条边都有一个方向，称这种树为有向树。对于T的顶点v来说，以点v为终点的边数称为点v的入度，以点v为起点的边数称为点v的出度。入度与出度之和称为点v的度。u7u5u4u3u2u1u6有向树T注：指出上图中顶点的入度、出度和度。0.810.60.40.20xt00.511.5210.500.51n20定义3：一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点。倒置根树T根树T注：根树常画成倒置形式，方向由上指向下。0.810.60.40.20xt00.511.5210.500.51n21定义4：对于根树T，顶点v到树根的距离称为点v的层数；所有顶点中的层数的最大者称为根树T的树高。上图中，根树高为3；倒置根树T2176435891011树根1：0层；点2，3，4：第1层；余类推。0.810.60.40.20xt00.511.5210.500.51n22计算机中数据结构常采用根树结构。族谱图是根树。定义5：对于根树T，若规定了每层顶点的访问次序，这样的根树称为有序树。注：一般次序为从左至右。有时也用边的次序代替顶点次序。定义6：对于根树T，由点v及其v的后代导出的子图，称为根树的子根树。倒置根树T2176435891011根树T的对应点2的子根树259100.810.60.40.20xt00.511.5210.500.51n23定义7：对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树。3元根树T2176435891011完全3元根树T2176435891011对于完全m元树T，有如下性质：定理2在完全m元树T中，若树叶数为t,分支点数为i,则：(1)1mit0.810.60.40.20xt00.511.5210.500.51n24证明：一方面，由树的性质得：另一方面，由握手定理得：()()1(1)mTit2()(1)(1)(2)mTtmim由(1)与(2)消去m(T)得：(1)1mit例6一台计算机，它有一条加法指令，可以计算3个数的和。如果要求9个数的和，问至少执行多少次加法指令？解：用3个顶点表示3个数，用一个父结点表示3个数的和。问题转化为求一棵有9个叶点的完全3元树的分支点数。0.810.60.40.20xt00.511.5210.500.51n25即：m=3,t=9,求i=?由定理2得：(31)91ii=4,至少要执行4次。两种可能情况是：x6x5x4x3x2x1x7x8x9x1x2x3x4x5x6x7x8x9在m元树中，应用最广泛的是二元树，原因是它在计算机中容易处理。0.810.60.40.20xt00.511.5210.500.51n26对于一棵有序树，常要转化为二元树。方法是：(1)从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线；(2)兄弟间用从左至右的有向边连接；(3)按如下方法确定二元树中结点的左右儿子：直接位于给定结点下面的儿子，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推。例7将下根树转化为二元树。v1v2v3v4v5v6v7v8v9根树Tv10v110.810.60.40.20xt00.511.5210.500.51n27解：v1v2v3v4v5v6v7v8v9v10v11v1v2v3v4v5v6v7v8v9v10v110.810.60.40.20xt00.511.5210.500.51n28二元树的遍历问题找到一种方法，能系统访问根结点，使得每个结点恰好访问一次。有三种常用方法：(1)先根次序遍历：1）访问根；2）按先根次序遍历根的左子树；3）按先根次序遍历根