定理7.13:霍夫曼算法得到的带权w1,w2,,wn的二分树是最优树。 分析:采用归纳法。 n=2,

Presentation on theme: "定理7.13:霍夫曼算法得到的带权w1,w2,,wn的二分树是最优树。 分析:采用归纳法。 n=2,"— Presentation transcript:

1 定理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最优树

2 引理1：设有一棵带权w1w2w3wk最优树，则必存在带权为w1,w2的树叶为兄弟的最优树。
, wn的最优树T’,则用子树 代替带权w1+w2的树叶，就是w1,w2,w3,,wk最优树。 现在证明该定理。

3 证明:采用归纳法。 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最优树

4 树是最小的连通图，删去任何一条边，必定不连通。

5 第八章　连通度，运输网络，匹配 8.1　连通度与块 为了衡量一个图的连通程度, 定义图的两个不变量: 点连通度和边连通度。

6 一、点连通度与边连通度 1. 点连通度 定义 8.1：设图G的顶点子集V'，若 (G-V')>(G)，则称V'为G的一个点割。|V'|=1时, V'中的顶点称为割点。 点割是集合，割点是顶点。 G2中，v就是割点，{v}就是点割。

7 定义8.2：设有图G，为产生一个不连通图或平凡图需要从 G 中删去的最少顶点数称为G的点连通度，记为(G)，简称G的连通度。
G是完全图Kn时, (Kn)=n-1。 必须说明的是(G)=1,G并不一定有割点

8 2.边连通度 定义8.3：设有图G, 为产生一个不连通图或平凡图需要从 G 中删去的最少边数称为G的边连通度，记为λ(G)。 显然, G是不连通图或平凡图时，λ(G)=0;； 连通图G有一桥时，λ(G)=1； G是完全图Kn时，λ(Kn)=n-1。

9 图的连通度有它的实际应用。设n个顶点表示n个站, 用e条边连接起来, 边表示通信线, 所谓连接好是指不易被破坏:
(1)使之具有最大的点连通度，这样当<κ(G)的点(结点)被炸毁时，其余各点仍然能够通信 (2)使之具有最大的边连通度, 这样当λ(G)的边(线路)被炸毁时，各点仍然能够通信

10 3.点连通度,边连通度与最小顶点度数联系。 定理 8.1:对任何一个图G，有κ(G)≤λ(G) ≤δ(G)。 证明：(1) λ(G) ≤δ(G) 若G是不连通图或平凡图，则λ(G)=0≤δ(G)，结论成立。 下面考虑G是; 连通图情况。 (2) κ(G)≤λ(G) 若G是不连通图或平凡图，则κ(G)=0=λ(G)，结论成立。 下面考虑G是连通图情况。

11 定义 8.4:若图G的κ(G)≥k，称G是k-连通的
非平凡连通图是1-连通的。 定义 8.5：若图G的边连通度λ(G)≥k$, 称G是k-边连通的。 例如图G3的边连通度是2, 所以它是2-边连通的, 也是1-边连通的；但不是3-边连通的。

12 二、割点与块 首先讨论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的路上。

13 定理 8.3：设G是顶点数n≥3的连通图, 下列论断是等价的:
定义 8.6：有割点的非平凡连通图称为可分图。没有割点的非平凡连通图称为不可分图。 顶点数n≥3的不可分图是2-连通图, 又称双连通图,

14 作业:P