离散数学试卷及答案(6)

离散数学试卷（六）35一、填空15%（每小题3分）1、n阶完全图结点v的度数d(v)=。2、设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。3、算式)*()*)*(((fedcba的二叉树表示为。4、如图给出格L，则e的补元是。5、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是。二、选择15%（每小题3分）1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（）。A、群；B、环；C、域；D、格。2、设[{a,b,c}，*]为代数系统，*运算如下：*abcaabcbbaccccc则零元为（）。A、a；B、b；C、c；D、没有。离散数学试卷（六）363、如右图相对于完全图K5的补图为（）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（）4度结点。A、1；B、2；C、3；D、4。5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（）时，[A，+，·]是整环。A、},2|{Znnxx；B、},12|{Znnxx；C、},0|{Zxxx且；D、},,5|{4Rbabaxx。三、证明50%1、设G是（n,m）简单二部图，则42nm。（10分）2、设G为具有n个结点的简单图，且)2)(1(21nnm，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（14分）4、],,[L是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）离散数学试卷（六）37四、10%设)()()(),,(323221321xxxxxxxxxE是布尔代数],,},1,0[{上的一个布尔表达式，试写出),,(321xxxE的析取范式和合取范式（10分）五、10%如下图所示的赋权图表示某七个城市721,,,vvv及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。一、填空15%（每小题3分）1、n-1；2、n(k+1)-2m；3、如右图；4、0；5、臂力小者二、选择15%（每小题3分）三、证明50%1、证：设G=（V，E）nnnnYnXYXV2121,,,对完全二部图有4)2()(2211211121nnnnnnnnnnnm当21nn时，完全二部图),(mn的边数m有最大值42n题目12345答案DCAAD离散数学试卷（六）38故对任意简单二部图),(mn有42nm。2、证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然nnn2111112121nnnnnn2)2)(1(2)2)(1(2)1(2)1(212211nnnnnnnnnm与假设矛盾。所以G连通。3、（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}，·]是半群乘：由“·”运算表知封闭群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（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；离散数学试卷（六）39当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}，+，·]是整环，故它是域。4、证：（1）“≤”是偏序关系，≤自然偏序abaLba,①反自反性：由代数格幂等关系：aaaaa。②反对称性：Lba,若abba,即：bababa,，则babbaaab③传递性：cbba,则：ababaabcbbacbaababacbaca即即结合律即cb)()(ca（2）Lyx,在L中存在{x,y}的下（上）确界设Lyx,则：},inf{yxyx事实上：yxyxxyxx)()(yyxxyx:同理可证离散数学试卷（六）40若{x,y}有另一下界c，则cycyxcyxc)()(yxcyx是{x,y}最大下界，即},inf{yxyx同理可证上确界情况。四、14%解：函数表为：1x2x3x),,(321xxxE00000011010001111000101111011111析取范式：)()()()()(),,(321321321321321321xxxxxxxxxxxxxxxxxxE合取范式：)()()(),,(321321321321xxxxxxxxxxxxE五、10%解：用库斯克（Kruskal）算法求产生的最优树。算法为：61615454434337337272277117123),(17),(3),(9),(4),(1),(vvevvwvvevvwvvevvwvvevvwvvevvwvvevvw选选选选选选结果如图：离散数学试卷（六）41树权C(T)=23+1+4+9+3+17=57（万元）即为总造价