资源描述:
《定理7.13霍夫曼算法得到的带权w1,w2,,wn的二分树是最.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、定理7.13:霍夫曼算法得到的带权w1,w2,,wn的二分树是最优树。分析:采用归纳法。n=2,结论成立假设n=k-1,结论成立。即用霍夫曼算法得到的带权w1,w2,,wk-1的二分树是最优树。对于n=k,用霍夫曼算法得到的带权w1,w2,,wk的二分树是最优树由归纳假设,用霍夫曼算法得到的带权w1+w2,w3,,wk的二分树是最优树。关键证明对于带权w1+w2,w3,,wk最优树,用子树代替带权w1+w2的树叶,就是w1,w2,w3,,wk最优树引理1:设有一棵带权w1w2w3wk最优树,则必存在带权为w1,w2的树叶为兄弟的最优树。引理2:若用霍夫曼算法可得到带
2、权w1+w2,,wn的最优树T’,则用子树代替带权w1+w2的树叶,就是w1,w2,w3,,wk最优树。现在证明该定理。证明:采用归纳法。n=2,结论成立假设n=k-1,结论成立。即用霍夫曼算法得到的带权w1,w2,,wk-1的二分树是最优树。对于n=k,由归纳假设,用霍夫曼算法得到的带权w1+w2,w3,,wk的二分树是最优树。由引理2得:对于带权w1+w2,w3,,wk最优树,用子树代替带权w1+w2的树叶,就是w1,w2,w3,,wk最优树树是最小的连通图,删去任何一条边,必定不连通。第八章 连通度,运输网络,匹配8.1连通度与块为了衡量一个图的连通程度,定义图的两个不
3、变量:点连通度和边连通度。一、点连通度与边连通度1.点连通度定义8.1:设图G的顶点子集V',若(G-V')>(G),则称V'为G的一个点割。
4、V'
5、=1时,V'中的顶点称为割点。点割是集合,割点是顶点。G2中,v就是割点,{v}就是点割。定义8.2:设有图G,为产生一个不连通图或平凡图需要从G中删去的最少顶点数称为G的点连通度,记为(G),简称G的连通度。显然,G是不连通图或平凡图时,(G)=0;连通图G有割点时,(G)=1;G是完全图Kn时,(Kn)=n-1。必须说明的是(G)=1,G并不一定有割点2.边连通度定义8.3:设有图G,为产生一个不连通图或平凡图需要从G中删
6、去的最少边数称为G的边连通度,记为λ(G)。显然,G是不连通图或平凡图时,λ(G)=0;;连通图G有一桥时,λ(G)=1;G是完全图Kn时,λ(Kn)=n-1。图的连通度有它的实际应用。设n个顶点表示n个站,用e条边连接起来,边表示通信线,所谓连接好是指不易被破坏:(1)使之具有最大的点连通度,这样当<κ(G)的点(结点)被炸毁时,其余各点仍然能够通信(2)使之具有最大的边连通度,这样当λ(G)的边(线路)被炸毁时,各点仍然能够通信3.点连通度,边连通度与最小顶点度数联系。定理8.1:对任何一个图G,有κ(G)≤λ(G)≤δ(G)。证明:(1)λ(G)≤δ(G)若G是不连通图或平凡图,则
7、λ(G)=0≤δ(G),结论成立。下面考虑G是;连通图情况。(2)κ(G)≤λ(G)若G是不连通图或平凡图,则κ(G)=0=λ(G),结论成立。下面考虑G是连通图情况。定义8.4:若图G的κ(G)≥k,称G是k-连通的例如图G3的点连通度是2,所以它是2-连通的,也是1-连通的,但不是3-连通的。非平凡连通图是1-连通的。定义8.5:若图G的边连通度λ(G)≥k$,称G是k-边连通的。例如图G3的边连通度是2,所以它是2-边连通的,也是1-边连通的;但不是3-边连通的。二、割点与块首先讨论2-连通图的特征。为此,先讨论一下割点。由定义8.4可知,有割点的连通图是1-连通的,但不是2-连通
8、的,反之亦然。割点有如下几个等价条件:定理8.2:设v是连通图G的一个顶点,下列论断是等价的:(1)v是G的一个割点。(2)对于顶点v,存在两个不同的顶点u和w,使顶点v在每一条从u到w的路上。(3)存在V-{v}的一个分成U和W的划分,使对任意两顶点uU和wW,顶点v在每一条从u到w的路上。定理8.3:设G是顶点数n≥3的连通图,下列论断是等价的:(1)G中没有割点。(2)G的任意两个顶点在同一条回路上。(3)G的任意一个顶点和任意一条边在同一条回路上。(4)G的任意两条边在同一条回路上。定义8.6:有割点的非平凡连通图称为可分图。没有割点的非平凡连通图称为不可分图。顶点数n≥3的
9、不可分图是2-连通图,又称双连通图,作业:P1871-11