《(完整word版)离散数学试卷及答案(8)》由会员分享，可在线阅读，更多相关《(完整word版)离散数学试卷及答案(8)（8页珍藏版）》请在金锄头文库上搜索。
1、离散数学试卷(八)填空15% （每小题3分）1、n阶完全图Kn的边数为2、的对偶图为3、nt，则边数m=4、的邻接矩阵A=#5、设 a,b,c, * 为代数系统，*运算如下:*abcaabcbbaccccc则它的幺元为 ;零元为 a、b、c的逆元分别为 选择15% （每小题3分）1、图相对于完全图的补图为（）。D对图A、1、2;则 k(G),(G),(G)分别为(C、2、1、2; D、1、2、2。3、一棵无向树 T有8个顶点,4度、3度、2度的分枝点各1个，其余顶点均为树叶，则中有()片树叶。A、3 ； B、4；C、5；4、设A , +, 是代数系统，其中+ , 为普通的加法和乘法， 则A=(
2、）时 是整环。A、x | x 2n,n Z;B、x | x 2n 1, n Z;C、x|x 0,且x Z;证明45%D、x | x a b4 5, a, b R。*关于A封闭的有(5、设A=1 , 2,，10 ，则下面定义的运算A、x*y=max(x ,y) ; B、x*y=质数 p 的个数使得 x p y ;C、x*y=gcd(x , y) ; (gcd (x ,y)表示 x 和 y 的最大公约数)；D、x*y=lcm(x ,y)(lcm(x ,y)表示x和y的最小公倍数)。2n1、设G是(n,m)简单二部图，则 m 。( 8分)412、 设G为具有n个结点的简单图，且 m (n 1)(n
3、2)则G是连通图。(8分)23、设G是阶数不小于11的简单图，贝U G或G中至少有一个是非平图。(14 分)4、记开”为1,关”为0,反映电路规律的代数系统0 , 1, +, 的加法运算和乘法运 算。如下:+01001丄丄丄I010000丄证明它是一个环，并且是一个域。（15分）四、生成树及应用10%1、（ 10分）如下图所示的赋权图表示某七个城市V1,V2, , V7及预先测算出它们之间的一些直接通信线路造价，试给出一个设 计方案，使得各城市之间既能够通信而且总造价最小。2、（ 10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW
4、 YEAR的编码信息。五、 5%对于实数集合 R,在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y或“ N”。MaxMin+可结合性可交换性存在幺元存在零兀01011 01、一n(n 1) ； 2、0112 01000110填空15% （每小题3分）没有4、2(nt1) ； 5、a, c, a、b、选择15% （每小题3分）题目12345答案AACDA，C三、证明45%1、(8 分)：设 G= (V, E), V X丫，凶厲，丫吐则 n1n2n对完全二部图有 m m n2n, n nJ(ni 弓)22当n1(n , m)的边数m有最大值n时，完全二部图2故对任意简单二部图(n
5、 , m)有m2、(8分)反证法：若 G不连通，不妨设G可分成两个连通分支Gi、G2,假设Gi和G2的顶点数分别为ni和n2，显然nin?n。n11 n21 mn i n2 n in 1( n11)n 2(n21) (n 1)( nin22) (n 1)( n 2)m -2 2 2 2与假设矛盾。所以 G连通。_ 11 10 一3、( 14 分)( 1 )当n=11时，G G Kii Kii边数m55条，因而必有G或G2的边数大于等于28，不妨设G的边数m 28，设G有k个连通分支，则G中必有回路。(否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi ,则kkmi n1,i1k ,nii
6、 1n11,i 1mimkk28mmi(m1)n k11 k矛盾)i 1i 1下面用反证法证明 G为非平面图。假设G为平面图，由于 G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g (g 3)条边围成，由点、边、面数的关系m (n k 1)，得：g 2离散数学试卷(八)27g328 m(11 k 1)(11 (k 1)3(11(11)3 113 2g 23 1而2827矛盾，所以G为非平面图。 I(2)当n11时，考虑G的具有11个顶点的子图g,则G或G必为非平面图。如果G为非平面图，则 G为非平面图。 I如果G为非平面图，则 G为非平面图。4、( 15 分)1) 0 ,
7、1, +, 是环 0 , 1, +是交换群乘：由“ +”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群： (0+0) +0=0+ (0+0) =0 ; (0+0) +仁0+ (0+1) =1；(0+1) +0=0+(1+0) =1; (0+1) +仁0+ (1+1) =0；(1 + 1) +1=1+ (1 + 1) =0 结合律成立。幺：幺元为0。逆：0, 1逆元均为其本身。所以， 0,1 , +是Abel群。 0 , 1, 是半群乘：由“”运算表知封闭群：(0 0) 0=0 ( 0 0) =0 ; ( 0 0) 1=0 (0 1) =1 ；(0 1) 0=0 (1 0) =1 ;
8、(0 1) 1=0 (1 1) =0；(1 1) 1=1 (1 1) =0 ; 对+的分配律对 x,y 0,1I 0 (x+y) =0=0+0=(0 x)+(0 y) n 1 ( x+y)当 x=y (x+y)=0 则#0 01 (x y) 1 0 0 1 1(1 0) (1 0)(11) (11)(1 x) (1 y)离散数学试卷（八）当xy ( xy 1 )则1 0(11)(1 0)1 (xy) 11 1(1 x) (1 y)0 1(10)(1 1)所以x, y, z0,1均有 z (xy)(zx) (zy)同理可证：（x y） z （x z） （y z）所以对+是可分配的。由得，0,1,
9、 +, 是环。（2）0，1，+， 是域因为0 , 1, +, 是有限环，故只需证明是整环即可。 乘交环：由乘法运算表的对称性知，乘法可交换。 含幺环：乘法的幺元是1 无零因子：1 1=1丰0因此0 , 1, + , 是整环，故它是域。四、树的应用20%1、（10分）解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图:树权C(T)=23+1+4+9+3+17=57 即为总造价 五、（10分）由二叉树知H A f I II EH、A、P、Y、N、E、W、R对应的编码分别为000、 001、 010、 011、 100、 101、 110、 111。显然000 , 001 , 010, 011, 100, 101 , 110, 111为前缀码。 英文短语 HAPPY NEW YEAR 的编码信息为000 001 010 010 011 100 101 001 001 101 001 111六、5%MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零兀NNN#
