离散数学-图论-Chapter03..ppt

第三章 树 3.1 树的有关定义 o 给定一个图G=(V,E), 如果它不含任何回 路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. o 无圈连通无向图称为树) o 定义3.1.1 一个不含任何回路的连通图称为树, 用T表 示. T中的边称为树枝, 度为1的节点称为树 叶. 树的基本应用 电线，水管， 煤气 有关度的若干术语 o 孤立点:度为0的顶点 o 悬点:度为1的顶点 n 悬边:与悬点关联的边 o 奇点:度为奇数的顶点 o 偶点:度为偶数的顶点 o 正则图:各顶点度相同 n 若度为k,称为k-正则图. n 例如:Kn是(n1)-正则图 树的有关定义 o 树的每条边, 都不会属于任何回路. 这样的 边叫割边. o 定义3.1.2 设e是G的一条边, 若G’=G-e比G的连通支 树连通支数增加, 则称e是G的一条割边. o 显然, 图G删去割边e=(u,v)之后, 结点u, v分属于不同的分支. 树的有关定义 o 定理3.1.1 e=(u, v)是割边,当且仅当e不属于G的任何回路. 证明: 必要性设e=(u, v)是割边, 此时若e=(u, v)属 于G的某个回路, 则G’=G-e中仍存在u到v的道路, 故结结点u和v属于同一连连通支, e不是割边边.矛盾. 充分性。

设设e不属于G的任何回路, 此时时若e不是割 边边, 则则G’=G-e与G的连连通支数一样样. 于是u和v仍 属于同一连连通支. 故G’中存在道路P(u,v), P(u,v)+e就是G的一个回路.矛盾. 树的有关定义 o定理3.1.2 设T是结点数为n≥2的树, 则下列性质等价: 1. T连通且无回路 2. T连通且每条都是割边 3. T连通且有n-1条边 4. T有n-1条边且无回路 5. T的任意两结点间有唯一道路 6. T无回路, 但在任两结点间加上一条边后恰有一个 回路 T连通且无回路T连通且每条都是割边 T连通且有n-1条边 o 12：T无回路，即T的任意边e都不属于回路， 由定理3.1.1，e是割边 o 23：对结点数n进行归纳令n(T), m(T)分别 表示树T的结点数和边数当n=2时命题成立设 n≤k时，m(T)=n(T)-1成立则n=k+1时， 由于任一边e都是割边，故G’=G-e有两个连通支 T1, T2由于n(Ti)≤k，i=1,2，故 m(Ti)=n(Ti)-1所以m(T)=n(T)-1也成立 3. T连通且有n-1条边 4. T有n-1条边且无回路 o 34：反证，假定T存在圈，去掉圈上一条 边，还是联通的，但m(T)=n-2，不能保证 联通了。

4. T有n-1条边且无回路 5. T的任意两结点间有唯一道路 o45：设u,v是T的任意两结点，先证道路P(u,v)的存在性，即证 明T是连通的 如果T不是连通的，则至少有两个连通分支T1, T2.由已知T中无回路 可知，T1, T2也没有回路根据1  2  3的证明，再由T1和T2是 连通的且无回路可得，m(T1)=n(T1)-1, m(T2)=n(T2)-1, 则 有： m(T)=m(T1)+m(T2)=(n(T1)+n(T2))-2=n-2w1而lkl1, 则有wkl1+w1lkwklk+w1l1. 所以将wk和 w1对调可得到T’，其满足WPL(T’)WPL(T), 与T最优矛盾 同时立即可知，w1必有兄弟否则让w1赋值给该树叶的父亲结点， 就可得到路径总长更小的树由于w2是序列中次最小的权，故可 令w1的兄弟是w2因此分支w1+w2可以是最优树T的子图 W1W2 W1+W2 定理3.6.1-证明(续) 设Tn是n个树叶的最优树，收缩分支w1+w2后 是对应的n-1个树叶的T’n-1. 在n-1个权(其中之一是w1+w2)时，也有其最 优二叉树Tn-1，然后将w1+w2分支展开后又 得到有n个权的二叉树T’n。

CLAIM. T’n-1和T’n都是最优树 当算法执行到n=2时，自然是一棵最优树再 与分支收缩的过程相反进行展开，最后得到 的T’n一定是最优二叉树 定理3.6.1-证明(续) CLAIM. T’n-1和T’n都是最优树 因为，Tn和Tn-1分别是最优树，所以 WPL(Tn)≤WPL(T’n)， WPL(Tn-1)≤WPL(T’n-1) 由于， WPL(T’n-1)=WPL(Tn)-(W1+W2)， WPL(Tn-1) =WPL(T’n)-(W1+W2) 所以有WPL(T’n-1)≤WPL(Tn-1) 同理有WPL(T’n)≤WPL(Tn) 定理3.6.1-证明(续) W1W2 Tn W1+W2 T’n-1 W1W2 Tn-1W1+W2 T’n   最佳前缀码－哈夫曼编码 哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应 用之一在电讯通信业务中，通常用二进制编码来表示字母或其 他字符，并用这样的编码来表示字符序列 例：如果需传送的电文为 ‘A B A C C D A’，它只用到四种字符， 用两位二进制编码便可分辨假设 A, B, C, D 的编码分别为 00， 01，10，11，则上述电文便为 ‘00010010101100’（共 14 位）， 译码员按两位进行分组译码，便可恢复原来的电文。

在编码过程通常要考虑两个问题 数据的最小冗余编码问题 译码的惟一性问题 Ø 数据的最小冗余编码问题 在实际应用中，各个字符的出现频度是不尽相同的，有些字符 出现的频率较高，有些字符出现的频率较低我们希望用较短的编 码来表示那些出现频率大的字符，用较长的编码来表示出现频率少 的字符，从而使得编码序列的总长度最小使得编码序列的总长度最小，使所需总空间量最少 这就是最小冗余编码问题 在上例中，若假设 A, B, C, D 的编码分别为 0，00，1，01， 则电文 ‘A B A C C D A’ 便为 ‘000011010’（共 9 位） 但此编码存在多义性：可译为 ‘A A A A C C A C A’、‘B B C C D A’、‘A B A C C D A’ 等 Ø 译码的惟一性问题 要求任一字符的编码都不能是另一字符编码的前缀！ 这种编码称为最佳前缀码前缀码（其实是非前缀码） 利用最优二叉树可以很好地解决上述两个问题 最佳前缀码 定义 设=12…n-1n是长度为n的符号串, 12…k称作的长度为k的前缀, k=1,2,…,n1. 若非空字符串1, 2, …, m中任何两个互不为前缀, 则称{1, 2, …, m}为前缀码 只出现两个符号(如0与1)的前缀码称作二元前缀码 例如 { 0, 10, 110, 1111 }, { 10, 01, 001, 110 }是二元前缀码 { 0, 10, 010, 1010 } 不是前缀码 用二叉树设计二进制前缀码 以电文中的字符作为叶子结点构造二叉树。

然后将二叉树中 结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每 个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列如 此得到的即为二进制前缀码 例： A B CD 0 1 0 1 0 1 编码： A：0 B：10 C：110 D：111 假设各个字符在电文中出现的次数次数（或频率）为 wi ，其编码编码 长度长度为 li，电文中只有 n 种字符，则电文编码总长电文编码总长为： 叶子结点的权 从根到叶子的路径长度 设计电文总长最短的编码 设计哈夫曼树（以 n 种 字符出现的频率作权） 用哈夫曼树设计总长最短的二进制前缀编码 由哈夫曼树得到的二进制前缀码称为哈夫曼编码 解： C B AD 0 0 0 1 1 1 编码： C：0 B：10 A：110 D：111 例：设 A, B, C, D 的频率（即权值）分别为 17％, 25％, 38％, 20％， 试设计哈夫曼编码（最佳前缀码） (如何理解最佳？) 1720 25 38 译码 从哈夫曼树根开始，对待译码电文逐位取码若编码是“0”， 则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出 一个字符；再重新从根出发，直到电文结束。

0 0 0 0 1 1 0 0 1 1 0 0 T ; A C S 电文为 “1101000” 译文只能是“CAT” 3.7 最短树(最小生成树) o在赋权连通图中，计算该图总长最小的支撑树， 即求最短树 o两种算法 nKruskal算法 nPrim算法 3.7.1 Kruskal算法 o 基本思想： 不断往T中加入当前的最短边e,如果此时会 构成回路，那么它一定是这个回路中的最 长边，删之直至最后达到n-1条边为止 这时T中不包含任何回路，因此是树 依据树的性质： 若T有n-1条边且无回路，则T是树 3.7.1 Kruskal算法 oKruskal算法的描述如下: T←Φ 当|T| n – 1且E≠Φ时时, begin 1. e←E中最短边边. 2. E←E-e. 3. 若T+e无回路,则则T←T+e. end 若|T|n-1打印”非连连通”, 否则输则输 出最短树树 Kruskal算法实例 1 243 56 6 1 6 5 55 6 3 4 2 图G 4 6 2 1 3 1 1 3 1 2 5 3 4 6 2 1 3 1 1 243 56 1 5 3 4 2 5 5 最短树 o 定理 3.7.1 T=(V, E’)是赋权连通图G=(V, E)的最短树, 当且仅当对任 意的余树边e∈E-E’, 回路Ce(CeE’+e), 满足其边权 w(e)≥w(a), a∈Ce(a≠e)． 证明:必要性. 如果存在一条余树边e,满足w(e)w(a), a∈Ce, 则T(a, e)得到新树T’比T更加短,与T是最短树矛盾. 1 243 56 1 5 3 4 2 5 1 243 56 6 1 6 5 55 6 3 4 2 图GT 3 最短树 o 充分性.即证明：设T=(V, E’)是G=(V, E)的一棵树，如 果对任意的余树边e∈E-E’, 回路Ce(CeE’+e), 满足其边 权w(e)≥w(a), a∈Ce(a≠e)，那么T是最短树。

反证若存在比T还短的树T’, 则T’-T≠, 设e∈T’-T, 则则 T+e构成唯一回路Ce. 根据已知，对对任意的T’关于T的余树树 边边e∈T’-T, 它与回路Ce里的树树枝边边a(a≠e)相比都有 w(e)≥w(a), 则则有w(T’)≥w(T), 与假设设矛盾. 注：因为为T和T’都是G的生成树树，所以结结点数和边边数都相同， 分别别是n和n-1 最短树 o 定理 3.7.2 Kruskal算法的计算复杂性是 O(m+p＊logm) 其中p是迭代次数． 3.7.2 Prim算法 o Prim算法的基本思想是： 首先任选一结点v0构成集合U, 然后不断在 V-U中选一条到U中某点(比如v)最短的边 (u,v)进入树T, 并且U=U+v, 直到U=V 最短树 oPrim算法的描述如下: 1. t←v1, T←, U←{t} 2. While U≠V do begin 3. W(t, u)=minv∈V-U{w(t, v)} 4. T←T+e(t, u) 5. U←U+u 6. For vV-U do W(t, v)←min{w(t, v), w(u, v)} end Prim 1)设G是n个顶点的连通无向图，T是零 树。

不妨设G中没有环，选。