运筹学_树.ppt

《运筹学_树.ppt》由会员分享，可在线阅读，更多相关《运筹学_树.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 图与网络分析2 树图和图的最小部分树树图和图的最小部分树1、树的性质树的性质2、图的最小部分树图的最小部分树3、最避圈法和破圈法一、树的概念和性质一、树的概念和性质例例5 乒乓球单打乒乓球单打比赛抽签后，可比赛抽签后，可用图表示。用图表示。无圈的连通图称为无圈的连通图称为树树，记作，记作 T(V,E)。树中次为。树中次为1的的称为树叶，次大于称为树叶，次大于1的称为分枝点。的称为分枝点。A B C D F G I J K L M NEH定理定理 图图T=(V,E),|V|=n,|E|=m,则下列关于树的说法是等价则下列关于树的说法是等价的。的。(1)T 是一个树。是一个树。(2)T 无

2、圈，且无圈，且 m=n-1。P152 性质性质2(3)T 连通，且连通，且 m=n-1。P152 性质性质3(4)T 无圈无圈,但每加一边即得惟一一个圈。但每加一边即得惟一一个圈。(5)T连通，但任舍去一边就不连通。连通，但任舍去一边就不连通。(6)T中任意两点有惟一链相连。中任意两点有惟一链相连。2-2、图的最小支撑树图的最小支撑树 (最小部分树最小部分树)P152 树图的边称为树枝树图的边称为树枝,不在生成树上的边称为弦不在生成树上的边称为弦.如边有权重如边有权重,树枝总长最小的生成树称为该图的树枝总长最小的生成树称为该图的最小支撑树最小支撑树.e1,e2,e3,e7,e8,e9为树为树枝

3、枝,定义定义15 若图若图G=(V,E)有生成子图是一棵树有生成子图是一棵树,则称该树为则称该树为G(a)e6 e3 e4 e2 e5 e1 e9 e8 e7(b)e7 e3 e2 e1 e 9 e8(b)为为(a)的生成树的生成树.e4,e5,e6为弦为弦.的的支撑树支撑树 (部分树部分树),。(c)e6 e4 e5(c)为为(b)的关于的关于(a)的补图的补图.2-2、图的最小支撑树图的最小支撑树 (最小部分树最小部分树)P152 定理定理 1 图图G=(V,E)中任一点中任一点 i,若若 j 是与是与 i 相邻点中距离最相邻点中距离最近的，则边近的，则边 i,j 一定必含在该图的最小生成

4、树内一定必含在该图的最小生成树内.推论推论:把图的所有点分成把图的所有点分成V和和V，两个集合，则两集合之间，两个集合，则两集合之间连线的最短边一定包含在最小则边连线的最短边一定包含在最小则边 i,j 一定必含在该图一定必含在该图的最小支撑树内的最小支撑树内.算法算法2 (避圈法避圈法)517723545124BADCSET517723545124BADCSET517723545124BADCSET517723545124BADCSET517723545124BADCSET517723545124BADCSET算法算法2 (避圈法避圈法)517723545124BADCSET517723545

5、124BADCSET517723545124BADCSET123512BADCSETmin w(T*)=14577544BADCSET w(T)=32算法算法2 (破圈法破圈法)1.从图中任选一圈；从图中任选一圈；2.去掉圈中最大权；去掉圈中最大权；517723545124BADCSET再检查剩余的图，重复再检查剩余的图，重复1，2.直至无圈为至。直至无圈为至。阅读 P151 -p155 P149 6.4(a),(c).作 业 算法算法2 (破圈法破圈法)1.从图中任选一棵树；从图中任选一棵树；2.由加上一条弦立即由加上一条弦立即生成一个圈，去掉圈生成一个圈，去掉圈中最大权；中最大权；得到一棵

6、新树，重得到一棵新树，重复复2.再检查剩余的再检查剩余的弦，直至全部弦检弦，直至全部弦检查完毕为至。查完毕为至。517723545124BADCSET找生成树的两种方法-深探法深探法(1)深探法深探法 在点集在点集V中任取一点中任取一点v,给给 v 以标号以标号 0.在某点在某点u集已得标号集已得标号i,检查一端点为检查一端点为u的各边的各边,另另一一若有(u,w)边之w未标号,则给w以标号i+1,记下边(u,w),若这样的边的另一端均已有标号,就退到标号为i-1的r直到全部点得到标号为止。012435678910 111213123456789101112130端点是否均已标号。端点是否均已

7、标号。记下边(u,w).令w代u,重复.点,以r 代u,重复.012345678910 111213找生成树的两种方法-广探法广探法(2)广探法广探法 在点集在点集V中任取一点中任取一点v,给给 v 以标号以标号 0.令令所有标号为所有标号为i的点集为的点集为V,检查检查V,VVi中的边端中的边端点是否均已点是否均已标号。对所有未标号之点均标以标号。对所有未标号之点均标以i+1,记记下这些边。下这些边。10122132122 343120对标号i+1的点重复步骤,直到全部点得到标号为至直到全部点得到标号为至.1212123332401111222223334三、最小生成树问题算法算法1 (Kr

8、uskal算法算法)例例7 一点一点v,给给 v 以标号以标号 0.1,1,1,1,2,2,2,3,3,4,4,4,4,5,5,5定义定义16 连通图连通图G=(V,E),每条边上有非负权每条边上有非负权L(e).一棵生一棵生1.权排序权排序v151121235445424v3v4v5v2v6v7v8v01v11121232v0v3v4v5v2v6v7v82.由小往大取线段，由小往大取线段，如与已取的成圈则弃之改取后者，如与已取的成圈则弃之改取后者，直至所有点连通。直至所有点连通。成树所有树枝上权的总和成树所有树枝上权的总和,称为这个生成树的权称为这个生成树的权.具有最具有最小小生成树称为生成

9、树称为最小生成树最小生成树(最小支撑树最小支撑树)简称简称最小树最小树.定理定理8 Kruskal算法所得子图是棵最小树。算法所得子图是棵最小树。算法算法2 (破圈法破圈法)1.从图中任选一棵树；从图中任选一棵树；v151121235445424v3v4v5v2v6v7v8v01v11121232v0v3v4v5v2v6v7v82.由加上一条弦立即由加上一条弦立即生成一个圈，去掉圈生成一个圈，去掉圈中最大权；中最大权；得到一棵新树，重得到一棵新树，重复复2.再检查剩余的再检查剩余的弦，直至全部弦检弦，直至全部弦检查完毕为至。查完毕为至。四、树根及其应用定义定义17 若一个有向图在不考虑边的方向

10、时是一棵树若一个有向图在不考虑边的方向时是一棵树,入次为入次为0的点称为根的点称为根,出次为出次为0的点称为叶的点称为叶,其它顶点称为分枝点其它顶点称为分枝点.则称则称这个有向图为有向树。这个有向图为有向树。定义定义18 有向树有向树T,恰有一个结点入次为恰有一个结点入次为0,其余各点其余各点入次均入次均为为1,则称则称T为根树。为根树。定义定义19 根树中根树中,若每个顶点的出次小于或等于若每个顶点的出次小于或等于m,称这棵称这棵树为树为m叉树。若每个顶点的出次恰好等于叉树。若每个顶点的出次恰好等于m或零或零,则称这则称这棵树为完全棵树为完全m叉树叉树.当当m=2时时,称为二叉树称为二叉树、

11、完全二叉树。完全二叉树。v1v4v3v2v5v6v7v8v9v10v11v1,v2,v3,v4,v8为分枝点为分枝点 v1为根为根v2,v3,v4 的层次为的层次为1,V11的层次为的层次为3.D A Huffman算法算法_B例例8 s=6,其权分别为其权分别为4,3,3,2,2,1,求最优二求最优二叉树。叉树。11.s个叶子按权由小至大排序个叶子按权由小至大排序2.最小权的二个叶子合并成最小权的二个叶子合并成将新分支点作为一个叶子。将新分支点作为一个叶子。叶子上带权的二叉树叶子上带权的二叉树,s 个叶子的权分别为个叶子的权分别为p i 根到各叶子根到各叶子算法算法 (D A Huffman

12、算法算法)m(T)=p i l ii=1s一个分支点，其权为二者之和一个分支点，其权为二者之和令令ss-1,若若s=1则停则停；否则转否则转(1).2323 4的距离的距离(层次层次)为为l i(i=1,s),二叉树的总权数：二叉树的总权数：3515961 232343568.9 最优检索问题最优检索问题5五类共五类共100万册，万册，A类类50万册，万册，B类类20万册，万册，C类类5万册，万册，算法算法 (D A Huffman算法算法)m(T)=p i l ii=1s10201550100D类类10万册，万册，E类类15万册，如何安排分检，使总运算万册，如何安排分检，使总运算(比较比较)次数最少？次数最少？1530505102015501001530508.9 最优检索问题最优检索问题五类共五类共100万册，万册，A类类50万册，万册，B类类20万册，万册，C类类5万册，万册，=1 50+220+315+410m(T)=p i l ii=1sD类类10万册，万册，E类类15万册，如何安排分检，使总运算万册，如何安排分检，使总运算(比较比较)次数最少？次数最少？=1750510201550100153050