成都理工大学2012

1、大题一二三四五六七八九十总分得分得分成都理工大学2012-2013学年第二学期离散数学考试试卷一、填空题(本大题共10小题，每小题2分，共20分)1、设G为9阶无向图，每个结点度数不是5就是6,则G中至少有个5度结点。2、n阶完全图，Kn的点数X (Kn)二。3、 有向图中从v1到v2长度为2的通路有条。4、设R, +,-是代数系统，如果R, +是交换群R,-是半群则称R, +, 为环。5、设L，是代数系统，则L，满足幕等律，即对V。G L有。 A上的关系R是自反的、对称和传递的，称R是A上的_等价关系。 群是一个存在二元运算可结合，存在单位元，每个元素存在逆元 的代数。若 h 是 A=S,米

2、到 A=S,米的同态，则h (a米b) =_h (a)米h (b)。R, +, 是环，则R, +是交换群，R,是_半群_。 一个无向图的欧拉回路要求经过图中每条边一次且仅一次，哈密尔顿回路要求经过图中每个顶点 一次且仅一次。巴分选择题（本大题共10小题，每小题2分，共20分）1、下面四组数能构成无向简单图的度数列的有（）。A、(2,2,2,2,2)；B、(1,1, 2, 2, 3)；C、(1,1,2,2,2)；D、(0,1, 3, 3, 3)。2、下图中是哈密顿图的为（）。3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（）A、真；B、假。4、下列偏序集（）能构成格。s = 1,

3、1,2,1,3,1,45、设 234, *为普通乘法，则S，*是（）。A、代数系统；B、半群；C、群；D、都不是。6.设 A = 1,2,3,4, A 上的关系 R = （1,1）,（2,3）,（2,4）,（3,4）,则 R 具有（）。A-自反性；B.传递性；C.对称性；D.以上都不是满足谓词P（x,y）： xy0的整数集Z上的二元关系具有（）性质？B、A-自反、对称B.对称、传递。.反对称D .反自反、对称、传递V=1, 2, 3, *, 1，x*y表示取x和y中较大数。下列不是V的 子代数的（）。A. 1, 2, 3, *, 1 B. 1, *, 1C. 2, 3, *, 1 D. 1,

4、3, *, 1A.2, 3；B . 2, 2, 2, 2；C10.3, 3, 3, 3； D . 1, 3, 3, 3。下列无向图中，不是二部图的是（D）。9.给定下列各序列，不能构成无向简单图的度数序列是（）。5Q得分一三、（本大题共40分）一1、（10%）在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5（12%）设B，x, +，_，1是布尔代数，定义运算*为a * b =（a x方）+ （。x b），

5、 求证B, *是阿贝尔群。得分四、（本大题共20分）_1、在二叉树中1）求带权为2, 3, 5, 7, 8的最优二叉树T。（10分）2）求T对应的二元前缀码。（10分）2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。302320答案:一、填空1、6； 2、n； 3、2； 4、+对分配且对+分配均成立；5、选择题目12345答案A,BB,DBCD三、证明1、（10分）证明：用n个顶点，vn表示n个人，构成顶点集V=v，vn，设E = uvIu，V e K 且 u,v 是朋友（u 牛 v），无向图 g=（V，e）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等

6、于2,结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结 点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n 顶点其度数取值只能是1，2,，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若u，v不连通则至少有两个连通分支GG2,使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定 理矛盾。因而u，v必连通。f=2-n+m=2-6-12=8Z deg（F） = 2 x m = 24由图论基本定理知：而岫气）Z 3，所以必有dW）=3，3 （8分）证

7、：n=6,m=12欧拉公式n-m+f=2知即每个面用3条边围成。4 （10分）证：设循环群A，的生成元为a同态映射为f，同态像为f （A），*，于是Pan,am e A都有 f (an -am) = f (an)* f (am)n=2,有 fg = f(a o) = f (q) * f(a) = (f (0)2若 n=k-l 时有 fg)=(f(g对 n=k 时，f (以)=f(以-1 . a) = f O-1) * f (o) =(o) =这表明，f(A)中每一个元素均可表示为(f0)n ,所以f(A),*为f(a)生成的循环群。5、证：交换律 寸。， 8 有1*力=(oxZ?) + (ix

8、Z?) = (Z?x3) + (Z? Xi) =Z?*o结合律：gb，cwB有(1 * Z?) * c = (g x 方)+(1 x /?) * c = (。xB) + (ax b) xc) + (a x 方)+ (1 x 人)x c =(a xb x c + a x b x c) + (a + b) x (a + b) x c= axbxc + axbxc + (axa + axb+bxa + bxb)xc=axbxc+axbxc+bxaxc + axbx c=axbxc + axb xc + axbxc + axb xc而：a * (Z? * c) = a * (Z? x c) + (方

9、x c)=(白 x (Z? x c) + (片 x c) + (a x(bxc) + (bx c) -ax(b+c)x(b + c)-haxbxc+axbxc= axbxc + axbxc+axbxc + axbx c(a*b)*c = a* (b*c)幺：有a0 = (ax0) +(ax0) = a + 0 = a 0*a = (0 x a) + (Ox a) = 0 + a = a。是8,*幺元。一、 、斗 /a e B a = (a xa) + (a xa) = 0 + 0 = Q理：。是。的逆元。综上所述：田，*是阿贝尔群。四、计算1、（10 分）（1）（5分）由Huffman方法，得最佳二叉树为:（2） （5 分）最佳前缀码为：000, 001, 01, 10, 112