离散数学试卷（五）参考答案 一、填空(15%)每空3分 1、6:2、n:3、2:4、+对·分配且·对+分配均成立：5、a⑧a=a且a田a=a 二、选择(15%)每小题3分 题目12345 答案ABB.DB D 三、证明(48%) 1、(10分)证明：用n个顶点n,.,Va表示n个人，构成顶点集V={M,.,a,设 E={wl4,veV,且u是朋友u≠v},无向图G=(V,E) 现证G中至少有两个结点度数相同。 事实上，(1)若G中孤立点个数大于等于2，结论成立。 (2)若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度 数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于1，由于G中顶点其度 数取值只能是1,2，-1，由鸽巢原理，必然至少有两个结点度数是相同的。 2、(8分)证：设G中两个奇数度结点分别为u,v。若山，v不连通则至少有两个连通分支G、 G2,使得u,V分别属于G1和G。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因 而u,V必连通 3(8分)证：n-6,m=12欧拉公式n-m+f2知f2-n+m=2-6-12=8 由图论基本定理知：∑degF)=2×m=24,而deg(F,)23,所以必有degF)=3,即每个 面用3条边围成。 4(I0分)证：设循环群[A,的生成元为a,同态映射为f,同态像为f(A),],于是a”,a"∈A 都有f(aa")=f(a)*f(a") 对n1有f(a)=f(a） n-2.f(a')=f(a.a)=f(a)*f(a)=(f(a))2
离散数学试卷（五）参考答案 32 一、填空（15%）每空 3 分 1、 6；2、n；3、2；4、+对·分配且·对+分配均成立；5、a a = a 且 a a = a 。 二、选择（15%）每小题 3 分 题目 1 2 3 4 5 答案 A,B B,D B C D 三、证明（48%） 1、（10 分）证明：用 n 个顶点 v1，.，vn 表示 n 个人，构成顶点集 V={v1，.，vn}，设 E ={uv | u,vV,且 u,v是朋友（u v）} ，无向图 G=（V，E） 现证 G 中至少有两个结点度数相同。 事实上，（1）若 G 中孤立点个数大于等于 2，结论成立。 （2） 若 G 中有一个孤立点，则 G 中的至少有 3 个顶点，既不考虑孤立点。设 G 中每个结点度 数均大于等于 1，又因为 G 为简单图，所以每个顶点度数都小于等于 n-1，由于 G 中 n 顶点其度 数取值只能是 1，2，.，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。 2、（8 分）证：设 G 中两个奇数度结点分别为 u，v。若 u，v 不连通则至少有两个连通分支 G1、 G2，使得 u，v 分别属于 G1 和 G2。于是 G1与 G2 中各含有一个奇数度结点，与握手定理矛盾。因 而 u，v 必连通。 3（8 分）证：n=6,m=12 欧拉公式 n-m+f=2 知 f=2-n+m=2-6-12=8 由图论基本定理知： deg(F) = 2m = 24 ，而 deg(Fi ) 3 ，所以必有 deg(Fi ) = 3 ，即每个 面用 3 条边围成。 4（10 分）证：设循环群[A，·]的生成元为 a，同态映射为 f，同态像为[f（A），*]，于是 a a A n m , 都有 ( ) ( )* ( ) n m n m f a a = f a f a 对 n=1 有 f (a) = f (a) n=2, 有 2 2 f (a ) = f (a a) = f (a)* f (a) = ( f (a))
离散数学试卷（五）参考答案 若n=k-1时有f(a)=(fa》- 对n=k时，f(a)=f(a.a=fa)*f(a)=(f(a》*fa）=(f(a》 这表明，fA)中每一个元素均可表示为(f(a)”，所以A),]为a)生成的循环群。 5、证： (1)交换律：a,b∈B有a*b=(a×b)+(a×b)=(b×a)+(5×a)=b*a (2)结合律：a,b,c∈B有 (a*b)*c=((axB)+(axb))*c=(((axB)+(axb))xc)+((axB)+(axb))xc =(a×bxc+a×b×c)+(a+b)×(a+b)×c =a×bxc+axb×c+(a×a+axb+b×a+bxb)xc =ax万xc+a×bxc+b×a×c+a×万xc =a×b×c+axb×c+a×b×c+a×bxc 而： a*(b*c)=a*(b×c)+(b×c》=(a×(b×c)+(b×c)+(a×(b×c)+(b×c》 =a×(b+c)x(b+c)+a×bxc+a×万xc =a×b×c+a×bxc+a×bxc+a×b×c ∴.(a*b)*c=a*(b*c) (3)么：a∈B有 a*0=(a×0)+(a×0)=a+0=a0*a=(0×a)+0×ad)=0+a=a .0是B,*]么元。 (4)逆：VaeB a*a=(axa)+(axa)=0+0=0 ∴a是a的逆元。 综上所述：B,门是阿贝尔群。 四、计算(22%) 1、(10分) (1)(5分)由Huffman方法，得最佳二叉树为：
离散数学试卷（五）参考答案 33 若 n=k-1 时 有 1 1 ( ) ( ( )) − − = k k f a f a 对 n=k 时， k k k k k f (a ) f (a a) f (a )* f (a) ( f (a)) * f (a) ( f (a)) 1 1 1 = = = = − − − 这表明，f(A)中每一个元素均可表示为 n ( f (a)) ，所以[f(A),*]为 f(a) 生成的循环群。 5、证： （1） 交换律： a,b B 有 a *b = (a b) + (a b) = (b a) + (b a) = b * a （2） 结合律： a,b,c B 有 a b c a b c a b c a b c a b c a b c b a c a b c a b c a b c a a a b b a b b c a b c a b c a b a b c a b c a b a b c a b a b c a b a b c = + + + = + + + = + + + + + = + + + + = + = + + + ( ) ( ) (( ) ( )) ( * ) * (( ) ( )) * ((( ) ( )) ) (( ) ( )) 而： a b c a b c a b c a b c a b c b c a b c a b c a b c a b c b c a b c b c a b c b c = + + + = + + + + = + = + + + ( ) ( ) *( * ) *(( ) ( )) ( ( ) ( )) (( ( ) ( )) (a *b) *c = a *(b *c) （3） 幺： a B 有 a *0 = (a 0) + (a 0) = a + 0 = a 0* a = (0 a) + (0 a) = 0 + a = a 0是[B，*]幺元。 （4） 逆： a B a * a = (a a) + (a a) = 0 + 0 = 0 a是a的逆元。 综上所述：[B，*]是阿贝尔群。 四、计算（22%） 1、（10 分） （1）（5 分）由 Huffman 方法,得最佳二叉树为：
离散数学试卷（五）参考答案 23 78 25 0 1 5 78 10 15 0 0 10 15 5 7 8 e 25 (2)(5分)最佳前缀码为：000,001,01,10,11 2、(12分) 图中奇数点为E、F,d(E)=3,dF)=3,dE,F)=28p=EGF 44— 35 复制道路EG、GF,得图G,则G是欧拉图。 由D开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为： 35+8+20+20+8+40+30+50+19+6+12+10+23=281。 34
离散数学试卷（五）参考答案 34 （2）（5 分）最佳前缀码为：000，001，01，10，11 2、（12 分） 图中奇数点为 E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF 复制道路 EG、GF，得图 G ‘，则 G ‘是欧拉图。 由 D 开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为： 35+8+20+20+8+40+30+50+19+6+12+10+23=281