复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）复习

514(1)若简单图G至多有2n个顶点每 个顶点度数至少为n,则G是连通图。(2)若 简单图G至多有2n个顶点每个顶点度数 至少为n-1,则G是连通图?为什么? 不一定 1517证明:对于任何简单图G,或者G是连 通的或者KG是连通的。 1521若G是一个多于四个顶点的任意简 单图,则或者G或者KG包含一条回路

[5.14](1)若简单图G至多有2n个顶点,每 个顶点度数至少为n,则G是连通图。(2)若 简单图G至多有2n个顶点,每个顶点度数 至少为n-1,则G是连通图? 为什么? 不一定 [5.17]证明:对于任何简单图G,或者G是连 通的或者K-G是连通的。 [5.21]若G是一个多于四个顶点的任意简 单图, 则或者G或者K-G包含一条回路

529](1)完全图Kn是欧拉图吗?是哈密 顿图吗? (2)完全二分图是欧拉图吗?是哈密顿图 吗

[5.29](1)完全图Kn是欧拉图吗? 是哈密 顿图吗? (2)完全二分图是欧拉图吗? 是哈密顿图 吗?

167设连通平面图G的顶点度数至少为3, 且其面数f12证明G有一个面的边数小 于5 68设图G的顶点度数至少为3,且面数 f12,则G是4面可着色的。 612设G是简单图,有n个顶点1)证明: 若n<8,则G与中至少有一个是平面图;

[6.7]设连通平面图G的顶点度数至少为3 , 且其面数 f<12,证明G有一个面的边数小 于5。 6.8 设图G的顶点度数至少为3，且面数 f<12，则G是4-面可着色的。 6.12 设G是简单图，有n个顶点(1) 证明： 若n<8，则G与中至少有一个是平面图；

6.14:求x(G)和x(G)

6.14:求(G)和*(G)

74(1)一棵树有两个顶点度数为2,一个 顶点度数为3,三个顶点度数为4问它有几 个度数为1的顶点? 有几个度数为1的顶点k问它 (2)一棵树有n个顶点度数为 (3)设n是树中度数为顶点数。证明: n1≥n;,(i=2,3,,△),或者 n2>n1≥n(i=3,4,…,△)

[7.4](1)一棵树有两个顶点度数为2, 一个 顶点度数为3,三个顶点度数为4,问它有几 个度数为 1 的顶点? (2)一棵树有ni个顶点度数为i,2ik,问它 有几个度数为 1的顶点? (3)设ni是树中度数为i的顶点数。证明: n1ni ,(i=2,3,…,),或者 n2>n1ni (i=3,4, …,)

721](1)试画一棵带权1,3,8,9,12,15,16的最 优二分树。 64 7 l61215 389 W(T)=(1+3)*5+8*4+9*3+(12+15+16)*2 =20+32+27+86=165

[7.21] (1)试画一棵带权1, 3, 8, 9, 12, 15, 16的最 优二分树。 W(T)=(1+3)*5+8*4+9*3+(12+15+16)*2 =20+32+27+86=165

(2)试将最优二分树的霍夫曼算法推广到最优m 分树上,其中m≥3。 当t-1不是m-1的倍数时,则添加k个权为0的,使t 1+k是m-1的倍数 画一棵最优m分树方法是: 这里t是权的个数 设个权w,W2,,ww1≤w2≤.,≤w1 首先构造棵树每棵树是一个顶点(即根)分别带 权w,w2,…,wt 然后找出m个带最小权w1,W2,wm的顶点作为 树叶,构造一棵m分树

(2)试将最优二分树的霍夫曼算法推广到最优 m 分树上, 其中m3。 当t-1不是m -1的倍数时, 则添加k个权为0的,使t- 1+k是m -1的倍数. 画一棵最优m分树方法是: 这里 t是权的个数 设t个权w1 ,w2 ,,wt ,w1w2wt 首先构造t棵树,每棵树是一个顶点(即根),分别带 权 w1 ,w2 , ,wt。 然后找出m个带最小权w1 ,w2 ,,wm的顶点作为 树叶, 构造一棵m分树

于是得到nm+1棵树,它们的根分别带权w+w2 +……+wm,Wm+1y…,wt 此时w1+w2+…,+ w<w不一定成立)。再在 tm+1棵树中找出m棵根带权最小的树,合并为 一棵新的m分树,使得这m棵树根带的权为原m 棵树根带的权之和,每一步选择m棵根带权最 小的树合并为一棵m分树,重复这一过程直到 只有一棵m分树为止

于是得到n-m+1棵树, 它们的根分别带权w1+w2 + +wm, wm+1,,wt , (此时w1+w2 ++wm wm+1不一定成立)。再在 t-m+1棵树中找出m棵根带权最小的树, 合并为 一棵新的m分树, 使得这m棵树根带的权为原m 棵树根带的权之和, 每一步选择m棵根带权最 小的树合并为一棵m分树, 重复这一过程直到 只有一棵m分树为止

(3)画一棵带权1,2,3,4,5,6,7,8,9的最优三分 树。 123789456 W(T)=(1+2+3)*3+(7+8+4+5+6)*2+9=87

(3)画一棵带权1, 2, 3, 4, 5, 6, 7, 8, 9的最优三分 树。 W(T)=(1+2+3)*3+(7+8+4+5+6)*2+9=87

(4)画一棵带权1,2,3,4,5,6,7,8的最优三分树。 8-1-7,加一个为0的权 023 5678 W(T)=(1+2)米3+(3+4+5+6+7)*2+8=67

(4)画一棵带权1, 2, 3, 4, 5, 6, 7, 8的最优三分树。 8-1=7,加一个为0的权. W(T)=(1+2)*3+(3+4+5+6+7)*2+8=67