33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G是循环群,令G=,?x,y?G,令x?ak,y?al,那么
xy?akal?ak?l?al?k?alak?yx,G是阿贝尔群
克莱因四元群,G?{e,a,b,c}
是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。 36.设?,?是5元置换，且
?12345??12345?????21453??，????34512??
????(1)计算??,??,??1,??1,??1??； (2)将??,??1,??1??表成不交的轮换之积。
(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。
?12345??12345??1?12345???解：(1) ???? ????45321??43125?? ????45123??
??????(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)。 解：点割集: {a,b},(d)
边割集{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?m31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。
?1?1?8(m?m)n(n?1)解：m?m? 得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的可达矩阵。 解：有向图D的邻接矩阵为：
?0??1A??0??1?0?0001??01??0100??000001?，A2??01??0100??00?201010???010??20??002??02010?A3??20??002??02?00200???200??020?200?
?020?004??(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有几个顶点
解：设3度分支点x个，则
5?1?3?2?3x?2?(5?3?x?1)，解得x?3
T有11个顶点
3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。
解：设4度分支点x个，则
8?1?2?3?4x?2?(8?2?x?1)，解得x?2
4、棵无向树T有ni (i=2，3，…，k )个i度分支点，其余顶点都是树叶，问T应该有几片树叶
解：设树叶x片，则
ni?i?x?1?2?(ni?x?1)，解得x?(i?2)ni?2 评论：2，3，4题都是用了两个结论,一是握手定理，二是m?n?1 5、n(n≥3)阶无向树T的最大度 至少为几？最多为几？ 解：2，n-1
6、若n(n≥3)阶无向树T的最大度 =2，问T中最长的路径长度为几？ 解：n-1
7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T都是二部图.
证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图 解：一阶无向树
14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质
解：e是桥
15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质
解：e是环
23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.；
证明：数学归纳法。k=1时, m = n-1，结论成立；
设k=t-1(t-1?1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树
任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）.
所以原图中m = n-k 得证。
24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树. (1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.
(2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统. (a) (b) 图16.16 解：(a)T的弦：c,d,g,h
T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有树枝: e,a,b,f
T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出
25、求图16.17所示带权图中的最小生成树.
(a) (b)
图16.17
解：
注：答案不唯一。
37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权. 38.下面给出的各符号串集合哪些是前缀码 A1={0，10，110，1111} 是前缀码 A2={1，01，001，000} 是前缀码 A3={1，11，101，001，0011} 不是前缀码 A4={b，c，aa，ac，aba，abb，abc} 是前缀码 A5={ b，c，a，aa，ac，abc，abb，aba} 不是前缀码 41.设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%
用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字.
解：
a:01 b:10 c:000 d:110 e:001 f:1111 g:1110