《离散数学》课程教学资源（试卷习题）试卷（答案）13

离散数学试卷（十三）参考答案 一、填空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 即运算☆具有可交换性。 所以是Abel群。 3、(10分)证明： 设是一环，且是关于同态映射f的同态象。 由是Abel群，易证也是Abel群。 是半群，易证也是半群。 现只需证：因对⊕是可分配的。 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)（） 因此也是环

离散数学试卷（十三）参考答案 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 即运算☆具有可交换性。 所以是 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 + 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}