《集合论与图论》第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
, 则不会出现上面
情况, 不会有边剩下. #