资源描述：
《离散数学试卷六试题与答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、试卷六试题与答案一、填空1.任何(n,m)图G=(V,E),边数与顶点度数的关系是。2.当n为时,非平凡无向完全图Kn是欧拉图。3.已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有个1度顶点。4．设，则r(R)=；s(R)=；t(R)=。5．设R为集合A上的等价关系，对，集合=，称为元素a形成的R等价类，，因为。6．任意两个不同小项的合取为，全体小项的析取式为。7．设，，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1）；（2）。8．含5个结点，4条边的无向连通
2、图（不同构）有个，它们是。9.设T为根树，若，则称T为m元树；若则称T为完全m叉树。二、选择1、下面四组数能构成无向图的度数列的有()。 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、图的邻接矩阵为()。A、；B、；C、；D、。3、下列几个图是简单图的有()。A.G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；B.G2=(V2,E2)其中V2=V1,E2={,,,,<
3、d,a>,}；C.G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}；D.G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列图中是欧拉图的有()。5、，其中，为集合对称差运算，则方程的解为（）。A、；B、；C、；D、。三、判断改正题：（每小题2分，本大题共20分）1．命题公式是一个矛盾式。（）2．任何循环群必定是阿贝尔群，反之亦真。（）3．根树中最长路径的端点都是叶子。（）4．若集合A上的关系R是对称的，则也是对称的。（
4、）5．数集合上的不等关系（≠）可确定A的一个划分。（）6．设集合A、B、C为任意集合，若A×B=A×C，则B=C。（）7．函数的复合运算“。”满足结合律。（）8．若G是欧拉图，则其边数合结点数的奇偶性不能相反。（）9．图G为（n,m）图，G的生成树必有n个结点。（）10．使命题公式的真值为F的真值指派的P、Q、R值分别是T、F、F。（）四.证明1、若图G中恰有两个奇数顶点，则这两个顶点是连通的。2、证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。3、某次会议有20人参加，其中每人至少有10个朋友
5、，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）五.根树的应用在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。六.设B4={e,a,b,ab}，运算*如下表，*则是一个群（称作Klein四元群）。答案一、填空15%（每小题3分）1、；2、奇数；3、54．，，，，，所以，。5．；。6．永假式（矛盾式），永真式（重言式）。7．（1）。（2）。8．3。9．每个结点的出
6、度都小于等于m；除叶子外，每个结点的出度都等于m。二.、选择15%（每小题3分）题目12345答案BCBBA三、判断改正题：1．×命题公式是一个重言式。2．×任何循环群必定是阿贝尔群，但反之不真。3．×根树中最长路径的端点不都是叶子。4．√5．×≠不能确定A的一个划分。6．√7．√8．×欧拉图其边数和结点数的奇偶性可以相反。9．√10．√四、证明1、证：设G中两个奇数度结点分别为u，v。若u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇
7、数度结点，与握手定理矛盾。因而u，v必连通。2、证：n=6,m=12欧拉公式n-m+f=2知f=2-n+m=2-6-12=8。由图论基本定理知：，而，所以必有，即每个面用3条边围成。3、解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，，，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。五、根树的应用解：用100乘各频率并由小到大排列得权数（1）用Huffman算法求最优二叉树：（1）前缀码用000
8、00传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。六、10%证明：（1）乘：由运算表可知运算*是封闭的。（2）群：即要证明，这里有43=64个等式需要验证但：①e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。③剩下只需验证含a、b等
