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

1、离散数学试卷六试题与答案试卷六试题与答案一、填空1 .任何(n,m)图G=(V,E),边数与顶点度数的关系是。2 .当n为时，非平凡无向完全图K.是欧拉图。3 .已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点，则T中有个1度顶点。4 设*=1,2,3,4,R=v1,2>,<2.4>,v3,3>,则r(R)=：s(R)=：t(R)=c5 .设R为集合A上的等价关系，对4，集合称为元素a形成的R等价类，团及工，因为。6 .任意两个不同小项的合取为，全体小项的析取式为。7 .设。(幻：工为偶数，P*)：x为素数，则下列命题：存在唯-偶素数：至多有-个偶素数：分

2、别形式化：(1):(2)。8 .含5个结点，4条边的无向连通图(不同构)有个，它们是。9 .设T为根树，若，则称T为m元树：二、若则称T为完全m叉树。三、选择1、下面四组数能构成无向图的度数列的有0。A、2,3,4,5,6,7：B、1,2,2,3,4：C、2,1,1,1,2：D、3,3,5,6,0。2 / 63、下列几个图是简单图的有0。r111，0 10 0、0100、00111101c、1I000,01011101D、Il0。）离散数学试卷六试题与答案A. Ei),其中=a,b,c,d,e,E：=ab,be,eb,ae,de):B. G产(W,EO其中V三V】，Er=<a»

3、b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>)：C. G=(VbEO,其V3=Vi,E户ab,be,ed»cc：D. G=(%,E),其中%=V“E；=(a,a),(a,b),(b,c),(e,c),(e,d)。4、下列图中是欧拉图的有0。D则方程L2工=1，3的解为（）oA、叽B、123（1,3：d、6三、判断改正题：（每小题2分，本大题共20分）1.命题公式（入八-8）-8是个矛盾式.（）2任何循环群必定是阿贝尔群，反之亦真。（）3 .根树中最长路径的端点都是叶子。（）4 .若集合A上的关系R是

4、对称的，则RT也是对称的。（）5 .数集合上的不等关系（W）可确定A的一个划分。（）6 .设集合A、B、C为任意集合，若AxB=AxC,则B=C。（）7 .函数的复合运算“。”满足结合律。（）8 .若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9,图G为（n.m）图，G的生成树乃必有n个结点。（）10.使命题公式Pf（QVR）的真值为F的真值指派的P、Q、R值分别是T、F、Fo()四.证明1、若图G中恰有两个奇数顶点，则这两个顶点是连通的。2、证明：在6个结点12条边的连通平面简的图中，每个面的面度都是3。3、某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席,用图

5、论知识说明是否可能每人邻做的都是朋友？（理由）五,根树的应用在通讯中，八进制数字出现的频率如下：0：30%、1：20%.2：15%.3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。六设B尸eab,ab,运算*如下表，eabcibeeabab则vB4.*是一个群（称aaeabb作Klein四元群）。答案h一、填空15%（每小题3分）”babea£d(v)=2m"bcibbae1、田：2、奇数：3、5Ar(R)=vl,2>,v2,4>,v3,3>,vl,l>,v2,2>,v4,4>s(R)=<1

6、,2>,<2,4>,<3,3>,<2,1>,<4,2>R2=R0R=<1,4>,v3,3>R3=R2oR=<3>/?4=/?3o/?=<3,3>)所以，f(H)=<1,2>,<2,4>,<3,3>,vl,4>_aR=xxeA,aRxaeaR6 .永假式(矛盾式)，永真式(重言式)。7 .(1)3x(<2(-)AP(x)A3y(C(y)aP(y)-x=y)(2)VxVy(2(x)aP(x)aC(y)aP(y)fx=y)。8 .3。<5Q9.每个结点

7、的出度都小于等于m：除叶子外，每个结点的出度都等于nu二、选择15%（每小题3分）题目12345答案BCBBA三、判断改正题：1. X命题公式(Aa(A-8)-8是个重言式。2. X任何循环群必定是阿贝尔群，但反之不真。3. X根树中最长路径的端点不都是叶子。4. V5.XH不能确定A的一个划分。6.77.，8. X欧拉图其边数”和结点数U的奇偶性可以相反。9.710.V四、证明1、证：设G中两个奇数度结点分别为u.vo若u.v不连通，即它们中无任何通路，则至少有两个连通分支G、G2,使得u,v分别属于Gi和G的于是Gi与G2中各含有一个奇数度结点,与握手定理矛盾。因而U,V必连通。2、证：n

8、=6.m=12欧拉公式nm+f=2知f=2n+m=2612=8。由图论基本定理知：Zdeg(F)=2x?=24而deg()>3所以必有deg(f)=3,即每个面用3条边围成。3、解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图五、G=<V，E>,20人用一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，deg(w)>10,deg(v)>10deg(z/)+deg(v)>20由判定定理，G中存在一条汉密尔顿回路c即所谈情况可能。六、根树的应用(1) 解：用100乘各频率并由小到大排列得权数(2) %=5,卬2=

9、5,%=5,叼=10,叼=10,卬6=15,叫=20,%=30用血后算法求最优二叉树：(3) 前缀码用00000传送5：00001传送6：0001传送7：100传送3：101传送4：001传送2：11传送1；01传送0(频率越高传送的前缀码越短)。六、10%证明：(1) 乘：由运算表可知运算*是封闭的。(2) 群：即要证明(X*')*Z=X*()'*Z),这里有43=64个等式需要验证但：e是幺元，含e的等式一定成立。ab=a*b=b*a,如果对含a,b的等式成立,则对含a、b、ab的等式也都成立。剩下只需验证含a、b等式，共有218个等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b：(a*b)*b=ab*b=a=a*(b*b)=a*e=a：(a*a)*a=e*a=a=a*(a*a)=a*e=a：(a*a)*b=e*b=b=a*(a*b)=a*ab=b：(b*b)*a=e*a=a=b*(b*a)