成都理工大学2012-2013离散数学期末试题

22f(a)?f(a?a)?f(a)*f(a)?(f(a))n=2, 有 k?1k?1f(a)?(f(a))若n=k-1时有

kk?1k?1k?1kf(a)?f(a?a)?f(a)*f(a)?(f(a))*f(a)?(f(a))对n=k时， n(f(a))这表明，f(A)中每一个元素均可表示为，所以[f(A),*]为f(a) 生成的循环群。

5、证：

（1） 交换律：（2） 结合律：

?a,b?B有a*b?(a?b)?(a?b)?(b?a)?(b?a)?b*a ?a,b,c?B有

(a*b)*c?((a?b)?(a?b))*c?(((a?b)?(a?b))?c)?((a?b)?(a?b))?c?(a?b?c?a?b?c)?((a?b)?(a?b))?c?a?b?c?a?b?c?(a?a?a?b?b?a?b?b)?c?a?b?c?a?b?c?b?a?c?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c而：

a*(b*c)?a*((b?c)?(b?c))?(a?(b?c)?(b?c))?((a?(b?c)?(b?c))?a?(b?c)?(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)

（3） 幺：?a?B有

a*0?(a?0)?(a?0)?a?0?a0*a?(0?a)?(0?a)?0?a?a

?0是[B，*]幺元。

（4） 逆：?a?Ba*a?(a?a)?(a?a)?0?0?0

?a是a的逆元。

综上所述：[B，*]是阿贝尔群。

四、计算

1、（10分）

（1）（5分）由Huffman方法,得最佳二叉树为：

（2）（5分）最佳前缀码为：000，001，01，10，11 2、（12分）

图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF 复制道路EG、GF，得图G‘

，则G‘

是欧拉图。 由D开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为：

35+8+20+20+8+40+30+50+19+6+12+10+23=281。