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

离散数学试卷（五）30一、填空15%（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有个5度结点。2、n阶完全图，Kn的点数X(Kn)=。3、有向图中从v1到v2长度为2的通路有条。4、设[R，+，·]是代数系统，如果①[R，+]是交换群②[R，·]是半群③则称[R，+，·]为环。5、设],,[L是代数系统，则],,[L满足幂等律，即对La有。二、选择15%（每小题3分）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、下列偏序集（）能构成格。离散数学试卷（五）315、设}4,41,3,31,2,21,1{s，*为普通乘法，则[S，*]是（）。A、代数系统；B、半群；C、群；D、都不是。三、证明48%1、（10%）在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设]1,0,,,,[B是布尔代数，定义运算*为)()(*bababa，求证[B，*]是阿贝尔群。四、计算22%1、在二叉树中1）求带权为2，3，5，7，8的最优二叉树T。（5分）2）求T对应的二元前缀码。（5分）2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。离散数学试卷（五）32一、填空（15%）每空3分1、6；2、n；3、2；4、+对·分配且·对+分配均成立；5、aaaaaa且。二、选择（15%）每小题3分题目12345答案A,BB,DBCD三、证明（48%）1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设},,,|{v）（uvuVvuuvE是朋友且，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，…，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3（8分）证：n=6,m=12欧拉公式n-m+f=2知f=2-n+m=2-6-12=8由图论基本定理知：242)deg(mF，而3)deg(iF，所以必有3)deg(iF，即每个面用3条边围成。4（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为[f（A），*]，于是Aaamn,都有)(*)()(mnmnafafaaf对n=1有)()(afafn=2,有22))(()(*)()()(afafafaafaf离散数学试卷（五）33若n=k-1时有11))(()(kkafaf对n=k时，kkkkkafafafafafaafaf))(()(*))(()(*)()()(111这表明，f(A)中每一个元素均可表示为naf))((，所以[f(A),*]为f(a)生成的循环群。5、证：（1）交换律：Bba,有abababbababa*)()()()(*（2）结合律：Bcba,,有cbacbacbacbacbacabcbacbacbbabbaaacbacbacbabacbacbacbabacbabacbabacba)())()(()())()(()))()(((*))()((*)*(而：cbacbacbacbacbacbacbcbacbcbacbcbacbcbacba)()())()((())()(())()((*)*(*)*(**)*(cbacba（3）幺：Ba有aaaaaaaaaa0)0()0(*00)0()0(0*。B，幺元是*][0（4）逆：Ba000)()(*aaaaaa。aa的逆元是综上所述：[B，*]是阿贝尔群。四、计算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉树为：离散数学试卷（五）34（2）（5分）最佳前缀码为：000，001，01，10，112、（12分）图中奇数点为E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF复制道路EG、GF，得图G‘，则G‘是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。