离散数学答案屈婉玲版第二版高等教育出版社课后答案
阶元,因为群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的同态。 证明：有已知?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}
?eabeeabecaabbccccb 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) ?????45321?? ?????43125?? ????45123??
???????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) 奇置换
第十四章部分课后习题参考答案
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条边的无向简单图只有两个：
所以，G1、G2、G3至少有两个是同构的。
离散数学答案屈婉玲版第二版高等教育出版社课后答案
20、已知n阶无向简单图G有m条边，试求G的补图G的边数m?。
解：m??n(n?1)?m 221、无向图G如下图
(1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度?(G)。
ae2be3解：点割集: {a,b},(d)
e1de5ee4c
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
k(G)=?(G)=1
23、求G的点连通度k(G)、边连通度?(G)与最小度数?(G)。
解：k(G)?2、?(G)?3 、?(G)?4
28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？
?3n?2m解：? 得n=6,m=9.
2n?3?m? 31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。
解：m?m??1?1?8(m?m)n(n?1) 得n? 2245、有向图D如图
(1)求v2到v5长度为1，2，3，4的通路数；
离散数学答案屈婉玲版第二版高等教育出版社课后答案
(2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。
v1v4v5v2v3
解：有向图D的邻接矩阵为：
?0??1A??0??1?0??0??4A4??0??4?0?0001??01??0100??000001?，A2??01??0100??00?201010???010??20??002??02010?A3??20??002??02?00200???200??020?200?
?020?004??0004??01??0400??520004? A?A2?A3?A4??21??0400??42?254040???215??522?215?
?522?254??(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0； (2)v5到v5长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10；
?1??1(4)出D的可达矩阵P??1??1?1?1111??1111?1111?
?1111?1111??第十六章部分课后习题参考答案