冷定理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 连通度与块 ❖ 为了衡量一个图的连通程度, 定义图的两个不 变量: ❖ 点连通度和边连通度