?eabceeabcaaecb bbcceacbae是交换群,但不是循环群,因为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??第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树.
2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有