图论最小生成树.pptx

1 图论及其应用图论及其应用应用数学学院应用数学学院2本次课主要内容本次课主要内容最小生成树最小生成树(一一)、克鲁斯克尔算法、克鲁斯克尔算法(二二)、管梅谷的破圈法、管梅谷的破圈法(三三)、Prim算法算法(四四)、计算机中的树简介、计算机中的树简介3最小连接问题：最小连接问题：交通网络中，常常关注能把所有站点连接起来的生交通网络中，常常关注能把所有站点连接起来的生成树，使得该生成树各边权值之和为最小。例如：成树，使得该生成树各边权值之和为最小。例如：假设要在某地建造假设要在某地建造5个工厂，拟修筑道路连接这个工厂，拟修筑道路连接这5处。处。经勘探，其道路可按下图的无向边铺设。现在每条边的经勘探，其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上，如果我们要求铺长度已经测出并标记在图的对应边上，如果我们要求铺设的道路总长度最短，这样既能节省费用设的道路总长度最短，这样既能节省费用，又能缩短，又能缩短工期工期，如何铺设？，如何铺设？v1v2v3v4v5122434554v1v2v3v4v51223不难发现：最小代价的连接方式为：不难发现：最小代价的连接方式为：最小连接问题的一般提法为：最小连接问题的一般提法为：在连通边赋权图在连通边赋权图G中求一棵总权值最小的生成树。中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。该生成树称为最小生成树或最小代价树。(一一)、克鲁斯克尔算法、克鲁斯克尔算法5克鲁斯克尔克鲁斯克尔(Kruskal):1928年生，一家年生，一家3弟兄都是数学家，弟兄都是数学家，1954年在普林斯顿大学获博士学位，导师是年在普林斯顿大学获博士学位，导师是Erds,他大他大部分研究工作是数学和语言学，主要在贝尔实验室工作。部分研究工作是数学和语言学，主要在贝尔实验室工作。1956年发表包含克鲁斯克尔算法论文，使他名声大振。年发表包含克鲁斯克尔算法论文，使他名声大振。1、算法思想、算法思想从从G中的最小边开始，进行避圈式扩张。中的最小边开始，进行避圈式扩张。2、算法、算法(1)、选择边、选择边e1,使得其权值最小；使得其权值最小；(2)、若已经选定边、若已经选定边e1,e2,ek,则从则从E-e1,e2,ek 中选择边中选择边ek+1,使得：使得：(a)、Ge1,e2,ek+1为无圈图为无圈图(b)、ek+1的权值的权值w(ek+1)尽可能小。尽可能小。6(3)、当、当(2)不能进行时，停止。不能进行时，停止。例例1 用克鲁斯克尔算法求下图的最小生成树。用克鲁斯克尔算法求下图的最小生成树。3v721546789101112v1v2v3v4v5v6v87解：过程如下：解：过程如下：1v5v821v1v5v8321v1v4v5v83v7215v1v4v5v83v72156v1v4v5v8v383v72156v1v4v5v8v3v683v72156v1v4v5v8v3v68v292、算法证明、算法证明定理定理1 由克鲁斯克尔算法得到的任何生成树一定是最小由克鲁斯克尔算法得到的任何生成树一定是最小生成树。生成树。证明：设证明：设G是一个是一个n阶连通赋权图，用阶连通赋权图，用T*=Ge1,e2,en-1表表示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小生成树。生成树。9 设设T是是G的一棵最小生成树。若的一棵最小生成树。若T*T由克鲁斯克尔算法容易知道：由克鲁斯克尔算法容易知道：TT*。于是令于是令f(T)=k 表示表示T*中的边中的边ei不在不在T中的最小中的最小i值。值。即可令即可令T=Ge1,e2,ek-1,ek,en 考虑：考虑：Teek k,则由树的性质，它必然为则由树的性质，它必然为G G中圈。中圈。作作 T1=T eek k-e,-e,容易知道：容易知道：T T1 1还为还为G G的一棵生成树。的一棵生成树。设设e是圈是圈T ek中在中在T中，但不在中，但不在T*中的边。中的边。由克鲁斯克尔算法知道：由克鲁斯克尔算法知道：所以：所以：这说明这说明T1是最小树，但这与是最小树，但这与f(T)的选取假设矛盾！所的选取假设矛盾！所以：以：T=T*.10 例例2 在一个边赋权在一个边赋权G中，下面算法是否可以产生有最小中，下面算法是否可以产生有最小权值的生成路？为什么？权值的生成路？为什么？算法算法:(1)选一条边选一条边e1,使得使得w(e1)尽可能小；尽可能小；(2)若边若边e1,e2,ei已经选定，则用下述方法从已经选定，则用下述方法从Ee1,.,ei中中选取边选取边ei+1：(a)G e1,e2,ei,ei+1为不相交路之并；为不相交路之并；(b)w(ei+1)是满足是满足(a)的尽可能小的权。的尽可能小的权。(3)当当(2)不能继续执行时停止。不能继续执行时停止。解：该方法不能得到一条最小生成路。解：该方法不能得到一条最小生成路。11 例如，在下图例如，在下图G中我们用算法求生成路：中我们用算法求生成路：3122343667910 用算法求出的生成路为：用算法求出的生成路为：12269312直接在图中选出的一条生成路为：直接在图中选出的一条生成路为：123366 后者的权值小于前者。后者的权值小于前者。(二二)、管梅谷的破圈法、管梅谷的破圈法 在克鲁斯克尔算法基础上，我国著名数学家管梅谷在克鲁斯克尔算法基础上，我国著名数学家管梅谷教授于教授于1975年提出了最小生成树的破圈法。年提出了最小生成树的破圈法。13 管梅谷（）。管梅谷（）。我国著名数学家，曾任山东我国著名数学家，曾任山东师范大学校长。中国运筹学会第一、二届常务理事，第六师范大学校长。中国运筹学会第一、二届常务理事，第六届全国政协委员。从事运筹学及其应用的研究，对最短投届全国政协委员。从事运筹学及其应用的研究，对最短投递路线问题的研究取得成果递路线问题的研究取得成果，冠名为中国邮路问题，该，冠名为中国邮路问题，该问题被列入经典图论教材问题被列入经典图论教材 和著作。和著作。管梅谷教授管梅谷教授1957年至年至1990年在山东师范大学工作。年在山东师范大学工作。1984年至年至1990年担任山东师范大学校长，年担任山东师范大学校长，1990年至年至1995年任复旦年任复旦大学运筹学系主任。大学运筹学系主任。1995年至今任澳大利亚皇家墨尔本理工年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员，国际项目办公室高级顾问及大学交通研究中心高级研究员，国际项目办公室高级顾问及复旦大学管理学院兼职教授。复旦大学管理学院兼职教授。自自1986年以来，管教授致力于城市交通规划的研究，在年以来，管教授致力于城市交通规划的研究，在我国最早引进加拿大的交通规划我国最早引进加拿大的交通规划EMME软件，取得一系列重软件，取得一系列重要研究成果要研究成果。14 破圈法求最小生成树的求解过程是：从赋权图破圈法求最小生成树的求解过程是：从赋权图G的任的任意圈开始，去掉该圈中权值最大的一条边，称为破圈。意圈开始，去掉该圈中权值最大的一条边，称为破圈。不断破圈，直到不断破圈，直到G中没有圈为止，最后剩下的中没有圈为止，最后剩下的G的子图为的子图为G的最小生成树。的最小生成树。证明可以参看证明可以参看数学的认识与实践数学的认识与实践4，(1975),38-41。3122343667910 例例3 用破圈法求下图用破圈法求下图G的最小生成树。的最小生成树。15312234366710 解：解：过程如下：过程如下：312234667103122366710312266710312266731226616(三三)、Prim算法算法 Prim算法是由算法是由Prim在在1957年提出的一个著名算法。年提出的一个著名算法。作者因此而出名。作者因此而出名。Prim(1921-)1949年在普林斯顿大学获博士学位，年在普林斯顿大学获博士学位，是是Sandia公司副总裁。公司副总裁。Prim算法：算法：对于连通赋权图对于连通赋权图G的任意一个顶点的任意一个顶点u，选择与点，选择与点u关关联的且权值最小的边作为最小生成树的第一条边联的且权值最小的边作为最小生成树的第一条边e1;在接下来的边在接下来的边e2,e3,en-1,在于一条已经选取的边只在于一条已经选取的边只有一个公共端点的的所有边中，选取权值最小的边。有一个公共端点的的所有边中，选取权值最小的边。用反证法可以证明该算法。即证明：由用反证法可以证明该算法。即证明：由Prim算法得算法得到的生成树是最小生成树。到的生成树是最小生成树。(证明略证明略)17 例例4 用用Prim算法求下图的最小生成树。算法求下图的最小生成树。554432176v1v2v3v4v5 解：过程如下：解：过程如下：1v1v231v1v2v318431v1v2v3v44321v1v2v3v4v5 最小生成树权值为：最小生成树权值为：w(T)=10.例例5 连通图连通图G的树图是指这样的图，它的顶点是的树图是指这样的图，它的顶点是G的生的生成树成树T1,T2,T,Ti与与Tj相连，当且仅当它们恰有相连，当且仅当它们恰有n-2条条公共边。证明任何连通图的树图是连通图。公共边。证明任何连通图的树图是连通图。证明：只需证明证明：只需证明,对任意对任意Ti与与Tj，在树图中存在连接它，在树图中存在连接它们的路即可！们的路即可！19 对任意对任意Ti与与Tj,设设e1,e2,ek(k n-2)是它们的公是它们的公共边。共边。由树的性质：由树的性质：使得：使得：。该圈中：。该圈中：作：作：则则Ti与与Ti+1有有n-2条边相同，于是，它们邻接。此时，条边相同，于是，它们邻接。此时，Ti+1与与Tj有有k+1条边相同。条边相同。如此这样作下去，可以得到连接如此这样作下去，可以得到连接Ti与与Tj的一条路为：的一条路为：所以，连通图所以，连通图G的树图是连通的。的树图是连通的。20(四四)、计算机中的树简介、计算机中的树简介 在计算机科学中，常常遇到所谓的根树。在计算机科学中，常常遇到所谓的根树。定义定义2：一棵树：一棵树T，如果每条边都有一个方向，称这种树，如果每条边都有一个方向，称这种树为有向树。对于为有向树。对于T的顶点的顶点v来说，以点来说，以点v为终点的边数称为终点的边数称为点为点v的入度，以点的入度，以点v为起点的边数称为点为起点的边数称为点v的出度。入度的出度。入度与出度之和称为点与出度之和称为点v的度。的度。u7u5u4u3u2u1u6有向树有向树T 注：指出上图中顶点的入度、出度和度。注：指出上图中顶点的入度、出度和度。21定义定义3：一棵非平凡的有向树：一棵非平凡的有向树T，如果恰有一个顶点的入，如果恰有一个顶点的入度为度为0，而其余所有顶点的入度为，而其余所有顶点的入度为1，这样的的有向树称，这样的的有向树称为根树。其中入度为为根树。其中入度为0的点称为树根，出度为的点称为树根，出度为0的点称为的点称为树叶，入度为树叶，入度为1，出度大于，出度大于1的点称为内点。又将内点和的点称为内点。又将内点和树根统称为分支点。树根统称为分支点。倒置根树倒置根树T根树根树T 注：根树常画成倒置形式，方向由上指向下。注：根树常画成倒置形式，方向由上指向下。22定义定义4：对于根树：对于根树T，顶点，顶点v到树根的距离称为点到树根的距离称为点v的层数；的层数；所有顶点中的层数的最大者称为根树所有顶点中的层数的最大者称为根树T的树高。的树高。上图中，根树高为上图中，根树高为3；倒置根树倒置根树T2176435891011 树根树根1：0层；层；点点2，3，4：第：第1层；余类推。层；余类推。23计算机中数据结构常采用根树结构。族谱图是根树。计算机中数据结构常采用根树结构。族谱图是根树。定义定义5：对于根树：对于根树T，若规定了每层顶点的访问次序，这，若规定了每层顶点的访问次序，这样的根树称为有序树。样的根树称为有序树。注：一般次序为从左至右。有时也用边的次序代替顶点注：一般次序为从左至右。有时也用边的次序代替顶点次序。次序。定义定义6：对于根树：对于根树T，由点，由点v及其及其v的后代导出的子图，称的后代导出的子图，称为根树的子根树。为根树的子根树。倒置根树倒置根树T2176435891011根树根树T的对应点的对应点2的子根树的子根树2591024定义定义7：对于根树：对于根树T，若每个分支点至多，若每个分支点至多m个儿子，称该个儿子，称该根树为根树为m元根树；若每个分支点恰有元根树；若每个分支点恰有m个儿子，称它为个儿子，称它为完全完全m元树。元树。3元根树元根树T2176435891011完全完全3元根树元根树T2176435891011对于完全对于完全m元树元树T，有如下性质：，有如下性质：定理定理2 在完全在完全m元树元树T中，若树叶数为中，若树叶数为t,分支点数为分支点数为i,则：则：25证明：一方面，由树的性质得：证明：一方面，由树的性质得：另一方面，由握手定理得：另一方面，由握手定理得：由由(1)与与(2)消去消去m(T)得：得：例例6 一台计算机，它有一条加法指令，可以计算一台计算机，它有一条加法指令，可以计算3个数的和。个数的和。如果要求如果要求9个数的和，问至少执行多少次加法指令？个数的和，问至少执行多少次加法指令？解：用解：用3个顶点表示个顶点表示3个数，用一个父结点表示个数，用一个父结点表示3个数的和。个数的和。问题转化为求一棵有问题转化为求一棵有9个叶点的完全个叶点的完全3元树的分支点数。元树的分支点数。26即：即：m=3,t=9,求求i=?由定理由定理2得：得：i=4,至少要执行至少要执行4次。两种可能情况是：次。两种可能情况是：x6x5x4x3x2x1x7x8x9x1x2x3x4x5x6x7x8x9 在在m元树中，应用最广泛的是二元树，原因是它在计算元树中，应用最广泛的是二元树，原因是它在计算机中容易处理。机中容易处理。27对于一棵有序树，常要转化为二元树。方法是：对于一棵有序树，常要转化为二元树。方法是：(1)从根开始，保留每个父亲同其最左边儿子的连线，撤从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线；销与别的儿子的连线；(2)兄弟间用从左至右的有向边连接；兄弟间用从左至右的有向边连接；(3)按如下方法确定二元树中结点的左右儿子：直接位于按如下方法确定二元树中结点的左右儿子：直接位于给定结点下面的儿子，作为左儿子，对于同一水平线上给定结点下面的儿子，作为左儿子，对于同一水平线上 与与给定结点右邻的结点，作为右儿子，依此类推。给定结点右邻的结点，作为右儿子，依此类推。例例7 将下根树转化为二元树。将下根树转化为二元树。v1v2v3v4v5v6v7v8v9根树根树Tv10v1128 解：解：v1v2v3v4v5v6v7v8v9v10v11v1v2v3v4v5v6v7v8v9v10v1129 二元树的遍历问题二元树的遍历问题 找到一种方法，能系统访问根结点，使得每个结点恰好找到一种方法，能系统访问根结点，使得每个结点恰好访问一次。有三种常用方法：访问一次。有三种常用方法：(1)先根次序遍历：先根次序遍历：1）访问根；访问根；2）按先根次序遍历根的左子树；）按先根次序遍历根的左子树；3）按先根次序遍历根的右子树；）按先根次序遍历根的右子树；即：先左后右！例如：即：先左后右！例如：v1v2v3v4v5v6v7v8v9v10v12v1130先根次序遍历次序为：先根次序遍历次序为：v1v2v4v6v7v3v5v8v9v10v11v12.(2)中根次序遍历：中根次序遍历：2）访问根；访问根；1）按中根次序遍历根的左子树；）按中根次序遍历根的左子树；3）按中根次序遍历根的右子树；）按中根次序遍历根的右子树；v1v2v3v4v5v6v7v8v9v10v12v11中根次序遍历次序为：中根次序遍历次序为：v6v4v7v2v1v8v5v11v10v12v9v3.31(3)后根次序遍历：后根次序遍历：3）访问根；访问根；1）按后根次序遍历根的左子树；）按后根次序遍历根的左子树；2）按后根次序遍历根的右子树；）按后根次序遍历根的右子树；v1v2v3v4v5v6v7v8v9v10v12v11后根次序遍历次序为：后根次序遍历次序为：v6v7v4v2v8v11v12v10v9v5v3v1.32 最优二元树最优二元树 定义定义8 设设T是一棵二元树，若对所有是一棵二元树，若对所有t片树叶赋权值片树叶赋权值wi(1it),it),且权值为且权值为w wi i的树叶层数为的树叶层数为L(wL(wi i),),称：称：为该赋权二元树的权。而在所有赋权为为该赋权二元树的权。而在所有赋权为wi的二元树中的二元树中W(T)最小的二元树称为最优二元树。最小的二元树称为最优二元树。哈夫曼算法：哈夫曼算法：(1)初始：令初始：令S=w1,w2,wt;(2)从从S中取出两个权值最小者中取出两个权值最小者wi与与wj,画结点画结点vi,带权带权wi,画画结点结点vj，带权，带权wj，画，画vi与与vj的父亲的父亲v，连接，连接vi与与v,连接连接vj与与v,令令v带权带权wi+wj;33(3)令令S=(S-wiwj)wi+wj;(4)判断判断S是否只含一个元素，若是，停止，否则转是否只含一个元素，若是，停止，否则转2).例例8 求带权为：求带权为：7、8、9、12、16的最优树。的最优树。解：由哈夫曼算法：解：由哈夫曼算法：7815(1)7815(2)91221912217815(3)1631912217815(4)16315234 作业作业 P43 习题习题2：16,17,1835Thank You!