定理霍夫曼算法市公开课一等奖省赛课获奖课件

定理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页引理1：设有一棵带权w1w2w3wk最优树，则必存在带权为w1,w2树叶为弟兄最优树。

引理2：若用霍夫曼算法可得到带权w1+w2,,wn最优树T’,则用子树代替带权w1+w2树叶，就是w1,w2,w3,,wk最优树。现在证实该定理。定理霍夫曼算法第2页证实:采取归纳法。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最优树

定理霍夫曼算法第3页树是最小连通图，删去任何一条边，必定不连通。定理霍夫曼算法第4页第八章连通度，运输网络，匹配8.1连通度与块为了衡量一个图连通程度,定义图两个不变量:点连通度和边连通度。定理霍夫曼算法第5页一、点连通度与边连通度1.点连通度定义8.1：设图G顶点子集V'，若(G-V')>(G)，则称V'为G一个点割。|V'|=1时,V'中顶点称为割点。点割是集合，割点是顶点。G2中，v就是割点，{v}就是点割。定理霍夫曼算法第6页定义8.2：设有图G，为产生一个不连通图或平凡图需要从G中删去最少顶点数称为G点连通度，记为(G)，简称G连通度。显然，G是不连通图或平凡图时,(G)=0;连通图G有割点时,(G)=1;G是完全图Kn时,(Kn)=n-1。必须说明是(G)=1,G并不一定有割点定理霍夫曼算法第7页2.边连通度定义8.3：设有图G,为产生一个不连通图或平凡图需要从G中删去最少边数称为G边连通度，记为λ(G)。显然,G是不连通图或平凡图时，λ(G)=0;；连通图G有一桥时，λ(G)=1；G是完全图Kn时，λ(Kn)=n-1。定理霍夫曼算法第8页图连通度有它实际应用。设n个顶点表示n个站,用e条边连接起来,边表示通信线,所谓连接好是指不易被破坏:(1)使之含有最大点连通度，这么当<κ(G)点(结点)被炸毁时，其余各点依然能够通信(2)使之含有最大边连通度,这么当λ(G)边(线路)被炸毁时，各点依然能够通信定理霍夫曼算法第9页3.点连通度,边连通度与最小顶点度数联络。定理8.1:对任何一个图G，有κ(G)≤λ(G)≤δ(G)。证实：(1)λ(G)≤δ(G)若G是不连通图或平凡图，则λ(G)=0≤δ(G)，结论成立。下面考虑G是;连通图情况。(2)κ(G)≤λ(G)若G是不连通图或平凡图，则κ(G)=0=λ(G)，结论成立。下面考虑G是连通图情况。定理霍夫曼算法第10页定义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-边连通。定理霍夫曼算法第11页二、割点与块首先讨论2-连通图特征。为此,先讨论一下割点。由定义8.4可知,有割点连通图是1-连通,但不是2-连通,反之亦然。割点有以下几个等价条件:定理8.2：设v是连通图G一个顶点,以下论断是等价:(1)v是G一个割点。(2)对于顶点v,存在两个不一样顶点u和w,使顶点v在每一条从u到w路上。(3)存在V-{v}一个分成U和W划分,使对任意两顶点uU和wW，顶点v在每一条从u到w路上。定理霍夫曼算法第12页定理8.3：设G是顶点数n≥3连通图,以下论断是等价:(1)G中没有割点。(2)G任意两个顶点在同一条回路上。(3)G任意一个顶点和任意一条边在同一条回路上。(4)G任意两条边在同一条回路上。