冷定理713:霍夫曼算法得到的带权w1W2,wn 的二分树是最优树 分析:采用归纳法。 ☆n=2, ∧入 结论成立 假设n=k-1结论成立。即用霍夫曼算法得到的带权 w1,w2,,wk-1的二分树是最优树。 对于n=k,用霍夫曼算法得到的带权w1,w2,wk的二分 树是最优树 由归纳假设,用霍夫曼算法得到的带权w1+w2,w3,,wvk 的二分树是最优树。 关键证明对于带权wl+w2,w3,,wk最优树,用子树代替 带权wl+w2的树叶,就是w1,w2,w3,,wk最优树
❖ 定理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:设有一棵带权w1≤w2≤w3≤.≤wk最优 树,则必存在带权为w1,w2的树叶为兄弟的 最优树。 引理2:若用霍夫曼算法可得到带权w+w2, ,w的最优树T,则用子树 代替带权w+w2的树叶,就是w1,W2w3…,wk 最优树。 现在证明该定理
❖ 引理1：设有一棵带权w1w2w3wk最优 树，则必存在带权为w1,w2的树叶为兄弟的 最优树。 引理2：若用霍夫曼算法可得到带权w1+w2 , , wn的最优树T’,则用子树 代替带权w1+w2的树叶，就是w1 ,w2 ,w3 ,,wk 最优树。 现在证明该定理
证明:采用归纳法。 ☆n=2, ∧入 结论成立 假设n=k-1结论成立。即用霍夫曼算法得到的带 权w1,w2,,wk1的二分树是最优树。 对于n=k,由归纳假设,用霍夫曼算法得到的带 权w1w2,w3,,wk的二分树是最优树。 由引理2得:对于带权wl+w2,w3,,wk最优树 用子树代替带权w+w的树叶,就是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最优树
树是最小的连通图,删去任何一条边,必定 不连通。 G1 G2 G3
❖ 树是最小的连通图，删去任何一条边，必定 不连通
第八章连通度,运输网络,匹配 8.1连通度与块 为了衡量一个图的连通程度,定义图的两个不 变量: 点连通度和边连通度
第八章 连通度，运输网络，匹配 ❖ 8.1 连通度与块 ❖ 为了衡量一个图的连通程度, 定义图的两个不 变量: ❖ 点连通度和边连通度
一、点连通度与边连通度 1.点连通度 冷定义81:设图G的顶点子集V,若o(G V)>o(G),则称V为G的一个点割。V|=1时, V中的顶点称为割点。 点割是集合,割点是顶点。 冷G中,v就是割点,v就是点割。 G2 G3
❖ 一、点连通度与边连通度 ❖ 1. 点连通度 ❖ 定义 8.1：设图G的顶点子集V'，若(GV')>(G)，则称V'为G的一个点割。|V'|=1时, V'中的顶点称为割点。 ❖ 点割是集合，割点是顶点。 ❖ G2中，v就是割点，{v}就是点割
定义8.2:设有图G,为产生一个不连通图或 平凡图需要从G中删去的最少顶点数称为G 的点连通度,记为K(G),简称G的连通度。 冷显然,G是不连通图或平凡图时,K(G)=0; 冷连通图G有割点时,K(G)=1; 冷G是完全图K时,K(Kn=n1 冷必须说明的是K(G)=1,G并不一定有割点
❖ 定义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中删去的最少边数称为G的边 连通度,记为(G)。 显然,G是不连通图或平凡图时,(G)=0; ☆连通图G有一桥时,(G)=1; 冷G是完全图Km时,(Kn)=n-1 G1 G2 G3
❖ 2.边连通度 ❖ 定义8.3：设有图G, 为产生一个不连通图或平 凡图需要从 G 中删去的最少边数称为G的边 连通度，记为λ(G)。 ❖ 显然, G是不连通图或平凡图时，λ(G)=0;； ❖ 连通图G有一桥时，λ(G)=1； ❖ G是完全图Kn时，λ(Kn)=n-1
图的连通度有它的实际应用。设n个顶点表示 n个站,用e条边连接起来,边表示通信线,所谓 连接好是指不易被破坏 (1)使之具有最大的点连通度,这样当<K(G) 的点(结点被炸毁时,其余各点仍然能够通 信 冷(2)使之具有最大的边连通度,这样当入G的边 (线路)被炸毁时,各点仍然能够通信
❖ 图的连通度有它的实际应用。设n个顶点表示 n个站, 用e条边连接起来, 边表示通信线, 所谓 连接好是指不易被破坏: ❖ (1)使之具有最大的点连通度，这样当<κ(G) 的点(结点)被炸毁时，其余各点仍然能够通 信 ❖ (2)使之具有最大的边连通度, 这样当λ(G)的边 (线路)被炸毁时，各点仍然能够通信
3点连通度,边连通度与最小顶点度数联系。 冷定理81:对任何一个图G,有K(G)AG)≤6(G) 冷证明:(1)G)≤6(G) 冷若G是不连通图或平凡图,则入G)=0≤6(G),结论成 立 下面考虑G是;连通图情况。 令(2)K(G)≤(G) 冷若G是不连通图或平凡图,则K(G)=0=(G),结论成 立。 下面考虑G是连通图情况
❖ 3.点连通度,边连通度与最小顶点度数联系。 ❖ 定理 8.1:对任何一个图G，有κ(G)≤λ(G) ≤δ(G)。 ❖ 证明：(1) λ(G) ≤δ(G) ❖ 若G是不连通图或平凡图，则λ(G)=0≤δ(G)，结论成 立。 ❖ 下面考虑G是; 连通图情况。 ❖ (2) κ(G)≤λ(G) ❖ 若G是不连通图或平凡图，则κ(G)=0=λ(G)，结论成 立。 ❖ 下面考虑G是连通图情况