离散数学试卷八试题与答案

试卷八试题与答案一、填空15%（每小题3分）1、n阶完全图Kn的边数为。2、右图的邻接矩阵A=。3、图的对偶图为。4、完全二叉树中，叶数为nt，则边数m=。5、设{a,b,c},*为代数系统，*运算如下：则它的幺元为；零元为；a、b、c的逆元分别为。二、选择15%（每小题3分）1、图相对于完全图的补图为（）。*abcaabcbbaccccc2、对图G则)(),(),(GGGk分别为（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。3、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、64、设A，+，·是代数系统，其中+，·为普通的加法和乘法，则A=（）时A，+，·是整环。A、},2|{Znnxx；B、},12|{Znnxx；C、},0|{Zxxx且；D、},,5|{4Rbabaxx。5、设A={1，2，…，10}，则下面定义的运算*关于A封闭的有（）。A、x*y=max(x,y)；B、x*y=质数p的个数使得ypx；C、x*y=gcd(x,y)；(gcd(x,y)表示x和y的最大公约数)；D、x*y=lcm(x,y)（lcm(x,y)表示x和y的最小公倍数）。三、证明45%1、设G是（n,m）简单二部图，则42nm。（8分）2、设G为具有n个结点的简单图，且)2)(1(21nnm则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（15分）四、生成树及应用10%1、（10分）如下图所示的赋权图表示某七个城市721,,,vvv及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。五、5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元存在零元答案：一、填空15%（每小题3分）1、)1(21nn；2、0110001011001010；3、；4、)1(2tn；5、a，c，a、b、没有二、选择15%（每小题3分）题目12345答案AACDA，C三、证明45%1、（8分）：设G=（V，E），nnnnYnXYXV2121,,,则对完全二部图有4)2()(2211211121nnnnnnnnnnnm当21nn时，完全二部图),(mn的边数m有最大值42n。故对任意简单二部图),(mn有42nm。2、（8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然nnn21。11112121nnnnnn2)2)(1(2)2)(1(2)1(2)1(212211nnnnnnnnnm与假设矛盾。所以G连通。3、（14分）（1）当n=11时，11KGG11K边数5521011'm条，因而必有G或G的边数大于等于28，不妨设G的边数28m，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则1,1kinmii,mmnnkiikii11,11kiikiikknnmm1111)1(28矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g(3g)条边围成，由点、边、面数的关系)1(2knggm，得：2723113))11(11(3))1(11(133)111(228kkggm而2728矛盾，所以G为非平面图。（2）当n11时，考虑G的具有11个顶点的子图'G，则'G或'G必为非平面图。如果'G为非平面图，则G为非平面图。如果'G为非平面图，则G为非平面图。4、（15分）1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+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；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0；…③·对+的分配律对}1,0{,yxⅠ0·（x+y）=0=0+0=(0·x)+(0·y)Ⅱ1·（x+y）当x=y(x+y)=0则)1()1()11()11()01()01(1100001)(1yxyx当yx（1yx）则)1()1()11()01()01()11(1001111)(1yxyx所以}1,0{,,zyx均有)()()(yzxzyxz同理可证：)()()(zyzxzyx所以·对+是可分配的。由①②③得，{0，1}，+，·是环。（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、P、Y、N、E、W、R对应的编码分别为000、001、010、011、100、101、110、111。显然{000，001，010，011，100，101，110，111}为前缀码。英文短语HAPPYNEWYEAR的编码信息为000001010010011100101001001101001111六、5%MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零元NNN