离散数学课后习题答案 - 屈婉玲(高等教育出版社) 下载本文

??10??10?11.设G=???01??,??0?1??,???????10???10????01??,??0?1???,证明G关于矩阵乘法构成一个群. ?????解:(1) ?x,y∈G, 易知xy∈G,乘法是Z上的代数运算。

(2) 矩阵乘法满足结合律

?10?(3)设??01??是单位元,

??(4)每个矩阵的逆元都是自己。 所以G关于矩阵乘法构成一个群.

14.设G为群,且存在a∈G,使得 G={ak∣k∈Z} 证明:G是交换群。

证明:?x,y∈G,设x?ak,y?al,则 xy?akal?ak?l??al?k?alak?yx 所以,G是交换群

17.设G为群,证明e为G中唯一的幂等元。

22?e0,即e0?e0e,由消去律知e0?e 证明:设e0?G也是幂等元,则e0

18.设G为群,a,b,c∈G,证明

∣abc∣=∣bca∣=∣cab∣ 证明:先证设(abc)k?e?(bca)k?e 设(abc)k?e,则(abc)(abc)(abc)?(abc)?e,

bc)(abc)?a(bc)aa?1?e 即 a(bc)(a左边同乘a?1,右边同乘a得

(bca)(bca)(bca)?(bca)?(bac)k?a?1ea?e

反过来,设(bac)?e,则(abc)?e.

kk由元素阶的定义知,∣abc∣=∣bca∣,同理∣bca∣=∣cab∣

21

19.证明:偶数阶群G必含2阶元。

证明:设群G不含2阶元,?a?G,当a?e时,a是一阶元,当a?e时,a至少是3阶元,因为群G时有限阶的,所以a是有限阶的,设a是k阶的,则a?1也是k阶的,所以高于3阶的元成对出现的,G不含2阶元,G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以,偶数阶群G必含2阶元

20.设G为非Abel群,证明G中存在非单位元a和b,a≠b,且ab=ba. 证明:先证明G含至少含3阶元。

若G只含1阶元,则G={e},G为Abel群矛盾;

若G除了1阶元e外,其余元a均为2阶元,则a2?e,a?1?a

?a,b?G,a?1?a,b?1?b,(ab)?1?ab,所以ab?a?1b?1?(ba)?1?ba,

与G为Abel群矛盾;

所以,G含至少含一个3阶元,设为a,则a?a2,且a2a?aa2。 令b?a2的证。

21.设G是Mn(R)上的加法群,n≥2,判断下述子集是否构成子群。 (1)全体对称矩阵 是子群 (2)全体对角矩阵 是子群

(3)全体行列式大于等于0的矩阵. 不是子群 (4)全体上(下)三角矩阵。 是子群

22.设G为群,a是G中给定元素,a的正规化子N(a)表示G中与a可交换的元素构成的集合,即

N(a)={x∣x∈G∧xa=ax} 证明N(a)构成G的子群。 证明:ea=ae,e?N(a)??

?x,y?N(a),则ax?xa,ay?ya

a(xy)?(ax)y?(xa)y?x(ay)?x(ya)?(xy)a,所以xy?N(a)

由ax?xa,得x?1axx?1?x?1xax?1,x?1ae?eax?1,即x?1a?ax?1,所以x?1?N(a) 所以N(a)构成G的子群

31.设?1是群G1到G2的同态,?2是G2到G3的同态,证明?1??2是G1到G3的同态。

22

证明:有已知?1是G1到G2的函数,?2是G2到G3的函数,则?1·?2是G1到G3的函数。 ?a,b?G1,(?1??2)(ab)??2(?1(ab))??2(?1(a)?1(b)) ?(?2(?1(a)))(?2(?1(b)))?(?1??2)(a)(?1??2)(b) 所以:?1·?2是G1到G3的同态。

33.证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群,并证明你的结论。 证明:设G是循环群,令G=,?x,y?G,令x?ak,y?al,那么

xy?akal?ak?l?al?k?alak?yx,G是阿贝尔群

克莱因四元群,G?{e,a,b,c}

?eeabeabecccaabbccb eacbae是交换群,但不是循环群,因为e是一阶元,a,b,c是二阶元。 36.设?,?是5元置换,且

????21453??,????34512??

????(1)计算??,??,??1,??1,??1??; (2)将??,??1,??1??表成不交的轮换之积。

(3)将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换。

?12345??12345??12345??12345??1?12345?????解:(1) ???? ???? ???????? 453214312545123???????1? ??1????????21534??54132??

?????12345??12345?(2) ???(1425) ??1?(14253) ??1???(143)(25) (3) ???(14)(12)(15) 奇置换, ??1?(14)(12)(15)(13) 偶置换 ??1???(14)(13)(25) 奇置换

第十四章部分课后习题参考答案

23

5、设无向图G有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G至少有多少个顶点?在最少顶点的情况下,写出度数列、?(G)、?(G)。 解:由握手定理图G的度数之和为:2?10?20

3度与4度顶点各2个,这4个顶点的度数之和为14度。 其余顶点的度数共有6度。

其余顶点的度数均小于3,欲使G的顶点最少,其余顶点的度数应都取2, 所以,G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,?(G)?4,?(G)?2. 7、设有向图D的度数列为2,3,2,3,出度列为1,2,1,1,求D的入度列,并求?(D),?(D),

??(D),??(D),??(D),??(D).

解:D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为1,1,1,2.

?(D)?3,?(D)?2,??(D)?2,??(D)?1,??(D)?2,??(D)?1

8、设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度点,问该图有多少个顶点?

解:由握手定理图G的度数之和为:2?6?12

设2度点x个,则3?1?5?1?2x?12,x?2,该图有4个顶点.

14、下面给出的两个正整数数列中哪个是可图化的?对可图化的数列,试给出3种非同构的无向图,其中至少有两个时简单图。

(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解:(1) 2+2+3+3+4+4+5=23 是奇数,不可图化; (2) 2+2+2+2+3+3+4+4=16, 是偶数,可图化;

18、设有3个4阶4条边的无向简单图G1、G2、G3,证明它们至少有两个是同构的。

证明:4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列为2,2,2,2;3,2,2,1;3,3,1,1。但3,3,1,1对应的图不是简单图。所以从同构的观点看,4阶4条边的无向简单图只有两个:

24