定理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的树叶为兄弟的最优树。 , 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 连通度与块 为了衡量一个图的连通程度, 定义图的两个不变量: 点连通度和边连通度。
一、点连通度与边连通度 1. 点连通度 定义 8.1：设图G的顶点子集V'，若 (G-V')>(G)，则称V'为G的一个点割。|V'|=1时, V'中的顶点称为割点。 点割是集合，割点是顶点。 G2中，v就是割点，{v}就是点割。
定义8.2：设有图G，为产生一个不连通图或平凡图需要从 G 中删去的最少顶点数称为G的点连通度，记为(G)，简称G的连通度。 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-连通的 非平凡连通图是1-连通的。 定义 8.5：若图G的边连通度λ(G)≥k$, 称G是k-边连通的。 例如图G3的边连通度是2, 所以它是2-边连通的, 也是1-边连通的；但不是3-边连通的。
二、割点与块 首先讨论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的路上。
定理 8.3：设G是顶点数n≥3的连通图, 下列论断是等价的: 定义 8.6：有割点的非平凡连通图称为可分图。没有割点的非平凡连通图称为不可分图。 顶点数n≥3的不可分图是2-连通图, 又称双连通图,
作业:P187 1-11