《集合论与图论》第21讲1 第21讲根树 ?1. 根树 ?2. 根树的周游 ?3. 最优树, Huffman算法 ?4. 最佳前缀码 《集合论与图论》第21讲2 根树(rooted tree) ?有向树: 基图是树的有向图 ?根树(rooted tree): 顶点分3类的有向树 树叶 内点 树根 ? ? 1 个数 01 >01 >00 分 支 点 出度入度名称 《集合论与图论》第21讲3 层数与树高 ?画法: 树根在最上方, 省略边的方向(从上 到下) ?顶点v的层数(level): L(v)=从树根到v路径 长度 ?树高(height): h(T)=顶点的最大层数 《集合论与图论》第21讲4 儿子,父亲,兄弟 ?儿子: u在上方与v相邻, v是u的儿子 ?父亲: u在上方与v相邻, u是v的父亲 ?兄弟: u与v有相同父亲, u是v的兄弟 ?祖先: 从u可达v, u是v的祖先 ?后代: 从u可达v, u是v的后代 《集合论与图论》第21讲5 有序树(ordered tree) ?有序树: 给相同层数的顶点标上次序的根 树 1 1 1 1 1 2 23 2 2 《集合论与图论》第21讲6 r叉树(t-ary tree) ?r叉树: ?v∈V(T), d + (v)≤r ?正则(regular)r叉树: ?v∈V(T), d + (v)=r ?完全(complete)正则r叉树: ?树叶v, L(v)=h(T) ?有序r叉树,有序正则r叉树,有序完全正则r 叉树 《集合论与图论》第21讲7 定理14.13 ?定理14.13: 设正则r(≥2)叉树T有i个分支 点和t个树叶, 则(r-1)i=t-1. ?证明: 当把一个树叶变为一个分支点时, 增加(r-1)个树叶, 所以t=(r-1)i+b. 当t=1时, i=0, 所以b=1. 所以t=(r-1)i+1. # ?证法2: 数学归纳法 《集合论与图论》第21讲8 根子树(rooted subtree) ?根子树: T是根树, v∈V(T), 由v本身及其 所有后代导出的子图T v ?左子树,右子树: 二叉树中分支点的左右 两个儿子导出的根子树 《集合论与图论》第21讲9 根树的周游(travesal) ?根树的周游: 列出根树的所有顶点, 每个 顶点恰好出现一次 ?中序行遍: 左子树, 根, 右子树 ?前序行遍: 根, 左子树, 右子树 ?后序行遍: 左子树, 右子树, 根 ?例: 中序: dbigjehacf 前序: abdegijhcf 后序: dijghebfca a b d e g c f h ji 《集合论与图论》第21讲10 四则运算式与二叉树 ?((a?(b+c))?d-e)÷(f+g)÷(h?(i+j)) ÷ ÷ ? ? ? - + + + a bc d ef g h ij 《集合论与图论》第21讲11 中缀法,前缀法,后缀法 ?中缀记法: ?前缀记法(波兰记法): ?后缀记法(逆波兰记法): ÷ ÷ ? ? ? - + + + a bc d ef g h ij 《集合论与图论》第21讲12 中缀法,前缀法,后缀法(例) 中缀: ((a?(b+c))?d-e)÷(f+g)÷(h?(i+j)) 前缀(波兰): ÷÷-??a+bcde+fg?h+ij 后缀(逆波兰): abc+?d?e-fg+÷hij+?÷ ÷ ÷ ? ? ? - + + + a bc d ef g h ij 《集合论与图论》第21讲13 通讯编码 ?Shannon, Hamming, Sudan ?有噪声信道的可靠通信: 编码 ?信息就是不确定性的消除: 熵(entropy) ?比特(bit): binary information unit ?例: {0,1,2,…,7}, log 2 8=3, 编码为 000,001,010,…,111 ?000111010101译为0725 《集合论与图论》第21讲14 不等长编码 ?若{0,1,2,…,7}出现频率不一样,则出现频 率高的用短码字 ?例: 频率递减: 0,1,2,3,4,5,6,7, 编码为 0,1,00,01,10,11,000,001. 若收到000111, 不能唯一解码: 651, 235, 075,…等. 原因: 码字互为前缀,如00是001的前缀 《集合论与图论》第21讲15 前缀码(prefix code) ?前缀码: 码字互相不为前缀的不等长编码 ?前缀码与二叉树对应 ?例:{0,1,2,3}编码为{00,010,011,1} ?收到000111,译为023 0 0 0 1 1 1 00 010 011 1 《集合论与图论》第21讲16 最佳前缀码 ?最佳前缀码: 给定信号出现频率, 平均码 字长度最短的前缀码 ?平均码字长度: 码字长度乘以频率,求和 ?例: {0,1,2,3}, 40%, 30%, 20%,10%, 编码1: {00,010,011,1}, 2×40%+3×30%+3×20%+1×10%=2.4 编码2: {1,00,010,011}, 1×40%+2×30%+3×20%+3×10%=1.9 《集合论与图论》第21讲17 最优二叉树 ?带权二叉树: 每个树叶v i 都指定实数权w i ?带权二叉树的权: W(T)=Σ t i=1 w i L(v i ), 树叶 是v 1 ,v 2 ,…,v t , 对应的层数是L(v 1 ),L(v 2 ),…, L(v t ) ?最优二叉树: 树叶权为w 1 ,w 2 ,…,w t 的所有 二叉树中权最小的一个(不唯一) ?求最优二叉树的算法: Huffman算法 《集合论与图论》第21讲18 Huffman算法 ?输入: 实数w 1 ,w 2 ,…,w t , ?输出: 树叶权为w 1 ,w 2 ,…,w t 的最优二叉树 ?算法: 1. 选择最小的2个权w 1 ,w 2 , 连接对 应的树叶得到权为w 1 +w 2 的分支点 2. 选择w 1 +w 2 ,w 3 ,w 4 , …,w t 中最小的2个 权, 连接对应顶点得到新的分支点和权 3. 同上重复进行, 直到只剩1个权为止 《集合论与图论》第21讲19 Huffman算法(举例) ?例14.9: 2,3,5,7,8 ?解: 2,3,5,7,8 // 5,5,7,8 // 10,7,8 // 10,15 // 25 // 25 10 15 7 8 5 5 25 10 15 7 8 25 25 10 15 25 10 15 7 8 5 5 2 3 W(T)=55. # 《集合论与图论》第21讲20 Huffman算法(正确性) ?定理14.11: 在带权为w 1 ≤w 2 ≤…≤w t 的所有 最优树中,一定有一棵最优树满足: 设带 权w 1 ,w 2 的顶点是v 1 ,v 2 , (1) v 1 ,v 2 是兄弟(2) v 1 ,v 2 的层数是树高h ?证明:最优树一定是正则树. 经过适当调换顶点, 一定可以满足要求. # 《集合论与图论》第21讲21 Huffman算法(正确性) ?定理14.12(Huffman): 设T’是带权为 w 1 +w 2 ,w 3 ,…,w t 的最优二叉树, 其中 w 1 ≤w 2 ≤…≤w t , 若把带权为w 1 +w 2 的树叶 作为分支点, 让2个儿子带权分别为w 1 ,w 2 , 记所得树为T*, 则T*是带权为w 1 ,w 2 , w 3 ,…,w t 的最优二叉树.# ?推广的Huffman算法: 最优r叉树. ?例14.11 《集合论与图论》第21讲22 总结 ?根树 ?根树的周游 ?最优树, Huffman算法 ?最佳前缀码 《集合论与图论》第21讲23 作业(#17) ? p256, 习题九, 18, 21 ? p370, 习题十四, 12 ?今天交作业#14,#15,#16 《集合论与图论》第21讲24 习题讲解(#11) ?p214, 习题七, 11,12,14,16 ?11. 证明: G?G ? m G =m G = m Kn /2 = n(n-1)/4 ? 4 | n(n-1) ? n=4k ∨ n=4k+1. # 《集合论与图论》第21讲25 习题讲解(#11) ?12. 证明: ?v, d Kn (v)=d G (v)+d G (v)=5, 由抽屉原则, 不妨设d G (v)≥3. 设r,s,t∈N G (v). (1) r,s,t中有2点在G中相邻. 不妨设 (r,s)∈E(G), 则r,s,v在G中彼此相邻. (2) r,s,t在G中彼此不相邻. 则r,s,t在G中彼 此相邻. # vv r s t r sv r s t 《集合论与图论》第21讲26 习题讲解(#11) ?14. 方法一: 直接证 ?证明: 简单图G非完全图, 所以有顶点s,t 在G中不相邻. G连通, 所以有路径Γ连接 s,t. 设Γ=v 0 v 1 …v k , 其中s=v 0 , t=v k (k≥2). v 0 与v 1 相邻, v 0 与v k 不相邻. 设v i 是与v 0 相 邻的下标i最大的顶点(0<i<k), 则v 0 与v i 相 邻,v i 与v i+1 相邻,并且v 0 与v i+1 不相邻. 令 u=v 0 ,v=v i ,w=v i+1 即可. # v 0 v k v i 《集合论与图论》第21讲27 习题讲解(#11) ?14. 方法二: 反证法 ?证明: (反证)假设:?u,v,w∈V(G), (u,v)∈E(G)∧(v,w)∈E(G) → (u,w)∈E(G). (即E(G)的传递性.) ?s,t∈V(G), G连通, 所以有路径Γ连接s,t. 利用上述传递性假 设可得(s,t)∈E(G). 由s,t的任意性得G是 完全图, 与G非完全图相矛盾! # s t 《集合论与图论》第21讲28 习题讲解(#11) ?14. 方法三: 短程线 ?证明: G非完全图,所以G中存在不相邻顶 点s,t. G连通, 所以在s,t之间一定有长度 ≥2的短程线. 在短程线上任取连续3点 u,v,w, 则u与v相邻,v与w相邻,并且u与w 一定不相邻(否则就可以跳过v, 与短程线 定义相矛盾). # uvw 《集合论与图论》第21讲29 习题讲解(#11) ?16.证明: 用扩大路径法易证: G中有长度 ≥δ+1≥4的圈. 设Γ=v 0 v 1 …v k 是极大路径, δ≥3, v 0 至少与Γ上的3个点相邻,设除v 1 外 的其余两点是v i ,v j (1<i<j≤k). 设|v 1 …v i |=s, |v i …v j |=t, 则|v 0 v 1 …v i v 0 |=s+2, |v 0 v i …v j v 0 |=t+2, |v 0 v 1 …v i …v j v 0 |=s+t+2. 利用最大公约数性质(a,b)=(a-b,b),得 ( s+2, t+2, s+t+2 ) = ( s+2, t+2, t ) = ( s+2, 2 ,t ) = 1或2. # v 0 v k v i v 1 v j st 《集合论与图论》第21讲30 习题讲解(#11) ?25. 强连通?有回路过所有顶点 ?存在顶点u和v, 从u到v有通路且从v到u 有边?从u到v有边(传递性!)且从v到u有 边, 与竞赛图任意两点之间只有一边矛盾. # uv 《集合论与图论》第21讲31 习题讲解(#12) ?p214, 习题七, 17, 18, 22, 23 ?17. 证法一: 定理13(前提条件是连通) ?证明: (1) G是完全图: κ(G)=δ(G)=n-1 (2) G非完全图: δ(G)=n-2, 易证G连通, 由 定理13得n-2 = δ(G) ≥κ(G) ≥ 2δ(G)-n+2= 2(n-2)-n+2 = n-2, ∴κ(G)=δ(G)=n-2. # ?证法二: 直接证 《集合论与图论》第21讲32 习题讲解(#12) ? 17. 证明: (1)G是完全图: κ(G)=δ(G)=n-1. (2)G非完全图: ?V’?V(G),|V’|<n-2,?u,v∈V(G)-V’, (2a) (u,v)∈E(G): (u,v)∈E(G-V’). (2b) (u,v)?E(G): δ(G)=n-2 ? d(u)=d(v)=n-2 ? ??w∈V(G)-V’ ∧ (u,w)∈E(G-V’) ∧ (w,v)∈E(G-V’) ? u,v连通? V’非割集?κ(G)≥n-2, 又n-2 = δ(G) ≥κ(G), ∴κ(G)=δ(G)=n-2. # 《集合论与图论》第21讲33 习题讲解(#12) ?18. (1) 证法一: 哈密顿图 ?证明: G简单∧δ(G)≥n/2 ? G是哈密顿图 ? G连通. # ?错误: (1) 利用定理13(前提是连通) (2) δ(G)≥n/2 ? m≥n-1 ? G连通. 注意: G连通? m≥n-1, 反之不然. 反例: G=K 4 ∪K 3 , m=9>n-1=6. 《集合论与图论》第21讲34 习题讲解(#12) ?18. (1) 证法二: 直接证(类似17题) ?证明: ?u,v∈V(G), (2a) (u,v)∈E(G). (2b) (u,v)?E(G): δ(G)≥n/2 ? d(u)≥n/2 ∧ d(v)≥n/2 ??w∈V(G) ∧ (u,w)∈E(G) ∧ (w,v)∈E(G) ? u,v连通? G连通. # 《集合论与图论》第21讲35 习题讲解(#12) ?18. (1) 证法三: 反证法 ?证明: 假设G不连通, 有s≥2个连通分支, 则至少有1个连通分支G 1 的顶点数n 1 ≤n/s, G是简单图, 所以 δ(G)≤n 1 -1≤n/s-1<n/s≤n/2, 矛盾! # 《集合论与图论》第21讲36 习题讲解(#12) ?18. (2) 证法一: 利用(1) ?证明: ?V’?V(G),|V’|<k,令G’=G-V’, δ(G’) ≥δ(G)-(k-1) ≥ (n+k-1)/2-(k-1) = (n-(k-1))/2 = n’/2 ? G’连通 ? V’非割集?κ(G)≥k ? G是k-连通图. # 《集合论与图论》第21讲37 习题讲解(#12) ?18. (2) 证法二: 直接证(类似(1)) ?证明: ?u,v∈V(G), δ(G)≥(n+k-1)/2 ? d(u)≥(n+k-1)/2 ∧ d(v)≥(n+k-1)/2, (2a) (u,v)∈E(G): ?w 1 ,w 2 ,…,w k-1 ∈V(G), (u,w i )∈E(G) ∧ (w i ,v)∈E(G) , i=1,2,…,k-1 (2b) (u,v)?E(G): ?w 1 ,w 2 ,…,w k ∈V(G), (u,w i )∈E(G) ∧ (w i ,v)∈E(G), i=1,2,…,k u,v之间有k条独立路径? G是k-连通图. # 《集合论与图论》第21讲38 习题讲解(#12) ?22. 说明: 区别: G是奇圈, G含奇圈 ?证明: 块是无割点极大连通子图. ?块G 1 , (1) G 1 无圈?V(G 1 )≤2, G 1 极大?G 1 =K 2 . (2) G 1 有圈?G 1 只有奇圈?G 1 只有1个奇圈 (反证,否则2圈相交必产生偶圈), G 1 无割点? G 1 是奇圈. # 奇偶 奇,偶? 《集合论与图论》第21讲39 习题讲解(#12) ?23. 证法一:定理14 证法二:直接构造 ?证明: G 1 =G 2 =K s+1 , V(G 1 )={u 1 ,u 2 ,…,u s+1 }, V(G 2 )={v 1 ,v 2 ,…,v s+1 }, V(G)=V(G 1 )∪V(G 2 )∪{w}, E(G)=E(G 1 )∪E(G 2 )∪{ (w,u i ),(w,v i ) | i=1,2,…,r }. # K s+1 K s+1 1 2 r 1 2 r 《集合论与图论》第21讲40 习题讲解(#12) ?23. 说明: 当r=s时, 不需要w: G 1 =G 2 =K s+1 , V(G 1 )={u 1 ,u 2 ,…,u s+1 }, V(G 2 )={u 1 ,v 2 ,…,v s+1 }, V(G)=V(G 1 )∪V(G 2 ), E(G)=E(G 1 )∪E(G 2 ). # K s+1 K s+1 《集合论与图论》第21讲41 习题讲解(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 ) ?2. (?) 每个块是欧拉图?每个块是边不 重的简单回路之并?G是边不重的简单回 路之并∧G连通?G是欧拉图 (?) 设G 1 和G 2 是有公共割点v的两个块, 只需证明d G1 (v)和d G2 (v)都是偶数. 《集合论与图论》第21讲42 习题讲解(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 ) ?2. (?续) G的欧拉回路每次经过v有4种 可能: (1)从G 1 到G 1 ,(2)从G 1 到G 2 ,(3)从G 2 到G 1 ,(4)从G 2 到G 2 , (2)(4)两种情况必然 成对出现, 所以d G1 (v)和d G2 (v)都是偶数. 每个块都连通,所以每个块都是欧拉图. # 《集合论与图论》第21讲43 习题讲解(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 ) ?3. (证法1: 删边) 任选2个奇数度顶点, 删 除它们之间的简单通路P 1 (G连通, 这样的 通路存在), 奇数度顶点减少2个. 在剩下 的含奇数度顶点的连通分支中重复上述 步骤, 分别得到P 1 ,P 2 ,…,P k . 如果还有剩 余连通分支,则都是欧拉图, 把相应的欧 拉回路合并到上述的简单通路中得到 P’ 1 ,P’ 2 ,…,P’ k . 则E(G)=∪ k i=1 P’ i . # 《集合论与图论》第21讲44 习题讲解(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 ) ?3. (证法2: 加边) 在k对奇数度顶点之间 加k条边, 就没有奇数度顶点了, 得到欧拉 图, 在欧拉回路中删除所加的k条边, 最多 得到k条的边不重简单通路. 如果得到少 于k条的边不重简单通路, 则随意拆断其 中一些, 以达到k条. # 《集合论与图论》第21讲45 习题讲解(#13) ? p234, 习题八, 2,3,4(更正: G-v 0 ) ?4. 只需证: 所有的圈都经过v 0 . (?)(反证)假设圈C不经过v 0 , 若每次都避 免走C上的边, 则最终就不能任意行遍(C 中边将剩下无法经过). (?) 所有的圈都经过v 0 , 则不会出现上面 情况, 不会有边剩下. #