定理：霍夫曼算法得到的带权w,w,,wn的分树是最优树分.ppt

定理7.13:霍夫曼算法得到的带权w1,w2,?,wn的二分树是最优树。 分析:采用归纳法。 n=2, 引理1：设有一棵带权w1?w2?w3???wk最优树，则必存在带权为w1,w2的树叶为兄弟的最优树。 证明:采用归纳法。 n=2, 树是最小的连通图，删去任何一条边，必定不连通。 第八章　连通度，运输网络，匹配 8.1　连通度与块 为了衡量一个图的连通程度, 定义图的两个不变量: 点连通度和边连通度。 一、点连通度与边连通度 1. 点连通度 定义 8.1：设图G的顶点子集V，若 ?(G-V)?(G)，则称V为G的一个点割。|V|=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 中删去的最少边数称为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是不连通图或平凡图，则λ(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-连通的。 二、割点与块 首先讨论2-连通图的特征。为此, 先讨论一下割点。由定义 8.4 可知,有割点的连通图是1-连通的, 但不是2-连通的, 反之亦然。割点有如下几个等价条件: 定理 8.2：设v是连通图G的一个顶点, 下列论断是等价的: (1) v是G的一个割点。 (2)对于顶点v, 存在两个不同的顶点u和w, 使顶点v在每一条从u到w的路上。 (3)存在V-{v}的一个分成U和W的划分, 使对任意两顶点 u?U和w?W，顶点v在每一条从u到w的路上。 定理 8.3：设G是顶点数n≥3的连通图, 下列论断是等价的: (1)G中没有割点。 (2)G的任意两个顶点在同一条回路上。 (3)G的任意一个顶点和任意一条边在同一条回路上。 (4)G的任意两条边在同一条回路上。 定义 8.6：有割点的非平凡连通图称为可分图。没有割点的非平凡连通图称为不可分图。 顶点数n≥3的不可分图是2-连通图, 又称双连通图, 作业:P187 1-11 * * 结论成立 假设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最优树 引理2：若用霍夫曼算法可得到带权w1+w2, ?, wn的最优树T’,则用子树 代替带权w1+w2的树叶，就是w1,w2,w3,?,wk最优树。 现在证明该定理。 结论成立 假设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.5：若图G的边连通度λ(G)≥k$, 称G是k-边连通的。 例如图G3的边连通度是2, 所以它是2-边连通的, 也是1-边连通的；但不是3-边连通的。 *