离散数学试卷（十三）参考答案 一、填空10%（每小题2分） 1、1,不存在：2、e≠0：3、a,beG有(a*b)*(a*b)=(a*a)*(b*b): e; Ps 1 0 0 0 -1 -1 0 5、它不包含与K:,:或Ks在2度结点内同构的子图。 二、进择10%（每小题2分） 题目12345 答案A,DB C D A 三、判断10% 题目12345 四、证明38% 1、(8分)证明： (1)设a,b,c∈A,b是a的右逆元，c是b的右逆元，由于b*(a*b)=b*e=b, e=b*c=b+(a*b)*c=(b*a)+(b+c)=(b*a)*e=b*a 所以b是a的左逆元。 (2)设元素a有两个逆元b、c,那么 b=b*e=b*(a*c)=(b*a)*c=e*c=c a的逆元是唯一的。 2、(12分)证明： [乘剩]八，一在A上封闭，运算☆在A上也封闭
离散数学试卷（十三）参考答案 85 一、 填空 10%（每小题 2 分） 1、1， 不存在；2、 e ；3、a,b G 有 (a *b) *(a *b) = (a * a) *(b *b) ； 4、 1 e 2 e 3 e 4 e 5 e 1 v 1 1 1 0 0 2 v -1 0 0 0 1 3 v 0 -1 0 1 -1 4 v 0 0 -1 -1 0 5、它不包含与 K3, 3 或 K5 在 2 度结点内同构的子图。 二、 选择 10%（每小题 2 分） 题目 1 2 3 4 5 答案 A，D B C D A 三、 判断 10% 题目 1 2 3 4 5 答案 Y Y N N N 四、 证明 38% 1、（8 分）证明： （1）设 a,b, c A，b 是 a 的右逆元，c 是 b 的右逆元，由于 b *(a *b) = b *e = b ， e = b *c = b *(a *b) *c = (b * a) *(b *c) = (b * a) *e = b * a 所以 b 是 a 的左逆元。 （2）设元素 a 有两个逆元 b、c，那么 b = b *e = b *(a *c) = (b * a) *c = e *c = c a 的逆元是唯一的。 2、（12 分）证明： [乘] ， ， −在A上封闭， 运算☆在 A 上也封闭
离散数学试卷（十三）参考答案 [群1ab.c∈A (a☆b)☆c=(aAb)v(aAb)☆c =(((anb)v(anb))nv((anb)v(anb)nc) =(anbne)v(anbne)v((avB)n(avB)nc) =(anbnc)v(anbnc)v(((anb)v(anb))nc) =(anbne)v(anbnc)v(anbnc)v(anbnc) 同理可得：a☆(b☆c)=(anbnC)v(anbnc)v(anbnc)v(anbAc) ∴.(a☆b)☆c=a☆(b☆c)即☆满足结合性 []a∈A,a☆0-0☆a=(0Aav(0Aa)=0vAa)=0va=a 故全下界0是A中关于运算☆的么元. [逆]aeA,(a☆a)=(aAa)v(aAa)=0v0=0 即A中的每一个元素以其自身为逆元。 I交]a☆b=(aAb)v(aAb)=(bAa)v(bAa)=b☆a 即运算☆具有可交换性。 所以<A,☆>是Abel群。 3、(10分)证明： 设<A,+,·>是一环，且<f八4)，田，⑧>是关于同态映射f的同态象。 由<A,+>是Abel群，易证<f(A),⊕>也是Abel群。 <A,·>是半群，易证<∫(4)，⑧>也是半群。 现只需证：因对⊕是可分配的。 b,b2,b∈f(4),则必有相应的a,a2,a,使得：fa,)=b,i=l,2,3于是 b⑧(b,©b)=fa)⑧(f(a2)©f(a)》=f(a)⑧(f(a,+a》 =f(a(a+a》=f(aa)+(aa》=f(aa)⊕f(aa3) =(f(a,)⑧fa2》©f(a)⑧f(a》 =(6⑧b)⊕(6⑧b) 同理可证(b⊕b)h=(b,b)（） 因此<f(A),田，⑧>也是环
离散数学试卷（十三）参考答案 86 [群] a,b,c A : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ((( ) ( )) ) ( ) ( ) (( ) ( ) ) ((( ) ( )) ) (( ) ( ) ) ( ) (( ) ( )) a b c a b c a b c a b c a b c a b c a b c a b c a b c a b c a b c a b a b c 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 a b c = = = = = = 同理可得 ☆ ☆ ☆ ☆ ☆ (a☆b)☆c = a☆(b☆c) 即☆满足结合性。 [幺] a A, a☆0 = 0☆a = (0 a) (0 a) = 0 (1 a) = 0 a = a 故全下界 0 是 A 中关于运算☆的幺元。 [逆] a A, (a☆a) = (a a) (a a) = 0 0 = 0 即 A 中的每一个元素以其自身为逆元。 [交] a☆b = (a b) (a b) = (b a) (b a) = b☆a 即运算☆具有可交换性。 所以<A, ☆>是 Abel 群。 3、(10 分) 证明: 设 A ,+ , • 是一环,且 f (A) , , 是关于同态映射 f 的同态象。 由 A ,+ 是 Abel 群，易证 f (A) , 也是 Abel 群。 A , • 是半群，易证 f (A) , 也是半群。 现只需证： 对 是可分配的。 b1 ,b2 ,b3 f (A),则必有相应的a1 ,a2 ,a3使得: f (ai ) = bi ,i =1,2,3 于是 ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( )) (( ) ( )) ( ) ( ) ( ) ( ) ( ( ) ( )) ( ) ( ( )) 1 2 1 3 1 2 1 3 1 2 3 1 2 1 3 1 2 1 3 1 2 3 1 2 3 1 2 3 b b b b f a f a f a f a f a a a f a a a a f a a f a a b b b f a f a f a f a f a a = = = + = + = = = + 同理可证 ( ) ( ) ( ) b2 b3 b1 = b2 b1 b3 b1 因此 f (A) , , 也是环
离散数学试卷（十三）参考答案 5、(8分)证明： 设G有r个面， 空g=2西d)2t0s15）2如2如即≤关 而r-e+r-2.故-e+经22即e≤-2 k-2 五、应用32% 1、(8分) 解：(G)即为最少考试天数 用Welch-Powell方法对G着色：gy,yy。 第一种颜色的点gy4V6,剩余点'，2g 第二种颜色的点V',剩余点g 第三种颜色的点y2 所以(G)≤3 任2yY,构成一圈，所以X(G)≥3 故x(G)=3 所以三天下午即可考完全部九门课程。 2、(8分) (0011) 解：AG)= 1010 0001 0100 0011 001 1011 01 i=1:A2,1]=1,A= 0001 i=2:A4,21, 0100
离散数学试卷（十三）参考答案 87 5、（8 分）证明： 设 G 有 r 个面， k e r e r k i r e k r r i r i i 2 deg( ) 2 , deg( ) (1 ) 2 1 = = 而 即 2 ( 2) 2 2 2, − − − + = − + = k k v e k r 而v e r 故v e 即 。 五、 应用 32% 1、（8 分） 解： (G) 即为最少考试天数。 用 Welch-Powell 方法对 G 着色： 9 3 7 1 2 4 5 8 6 v v v v v v v v v 第一种颜色的点 9 1 4 6 v v v v ，剩余点 3 7 2 5 8 v v v v v 第二种颜色的点 3 7 5 v v v ，剩余点 2 8 v v 第三种颜色的点 2 8 v v 所以 (G) ≤3 任 2 3 9 v v v 构成一圈，所以 (G) ≥3 故 (G) =3 所以三天下午即可考完全部九门课程。 2、（8 分） 解： = 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 A(G) i = 1：A[2，1]=1， = 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1 1 A ； i = 2： A[4，2]=1， = 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 A
离散数学试卷（十三）参考答案 (001) i=3:A1,3FA2,3=A4,3=l, 4=1011 0001 1111 1111 1111 1111 p中的各元素全为1，所以G是强连通图。 当然是单向连 通和弱连通。 3、(8分) 解：用abc,dcg7个结点表示7个人，若两人能交谈可用 条无向边连结，所得无向图为 此图中的Hamilton回路即是圆桌安排座位的顺序。 Hamilton回路为abd fgeca. 4、(8分) 解：(1) 2 35 78 6 5 7 10 7 10 15 15 34 W(T)=2×4+3×4+5×3+9×2+7×2+8×2=83 (1)用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为{0000,0001,001,01,10,11}
离散数学试卷（十三）参考答案 88 i = 3： A[1，3]=A[2，3]=A[4，3]=1， = 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 A i = 4： A[k，4]=1，k=1，2，3，4， = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A p 中的各元素全为 1，所以 G 是强连通图，当然是单向连 通和弱连通。 3、（8 分） 解：用 a,b,c,d,e,f,g 7 个结点表示 7 个人，若两人能交谈可用一 条无向边连结，所得无向图为 此图中的 Hamilton 回路即是圆桌安排座位的顺序。 Hamilton 回路为 a b d f g e c a。 4、（8 分） 解：(1) W (T) = 2 4 + 3 4 + 53 + 9 2 + 7 2 + 8 2 = 83 （1） 用 0000 传输 a、0001 传输 b、001 传输 c、01 传输 f、10 传输 d、11 传输 e 传输它们的最优前缀码为{0000，0001，001，01，10，11}