离散数学(a)答案2015

《离散数学(a)答案2015》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、杭州师范大学钱江学院2014-2015学年第二学期期末试卷班《离散数学》(A)卷命题教师田止平题目—二三四五总分分值2020202020100得分一、判断题(对的打s错的打x；每空2分，共20分)得分1、“若鸟不会飞，则地球比太阳大。”是假命题。(X)2、一p/(p―g)=>―q□(X)3、3x(A(%)aB(x))=>BxA(x)aBxB(x)(v)4、有限偏序集(X,5)必定存在最小元。(x)5、对称关系不一定是反对称关系。(v)Q01、6、设集合X二｛g",c｝上的关系/?的关系矩阵是Mr=111,则关系/?是等,001,价

2、关系。(x)7、图G是n阶简单图，若对所有的vgV=>df(v)>l,则在G中有回路。(v)8、在哈密顿图G中若顶点u和v不相邻，则必有d(u)+d(v)>n.(X)宗9、平面图G是n阶简单连通图，它有e条边，则e<3n-60(v)W10、有n—l条边的n阶图是树。(X)得分二、填空题(每空4分，共20分)K将命题：“每列火车都比某些汽车快。”符号化。设个体域为交通工具。P(x)：x是火车；Q(x)：x是汽车；R(x,y)：x比y快。则“每列火午都比某些汽车快。”可以符号化为：Vx3^(P(x)人Q(y)tR(兀,y))2、全序关系

3、(X,<)o集合X匕的自反，反对称和传递关系称为X上的偏序关系，如果对于X中的任意两个元素都是可以比较的，那么就称为全序关系。3、简单回路。图的一条回路，如果其中所有的边都不相同，那么就称为简单凹路。4、超立方图Q”的色数龙(Q“)=2。5、在简单图G(V,E)中,E

4、=

5、v

6、-3,则图G(V,E)的联通分支数co(G)=3。得分三、选择题(每题4分，共20分)1、下而命题公式中，矛盾式是(C)(A)Pt(PvQ)(C)(PV-!P)(2A-10A/?)(D)(P*)T(「P㈠一2、设集合X={1,2,3,4,6,10,12}上的关

7、系/?是整除关系，则关系/?(C)(A)有最大元，有最小元(B)有最大元，无最小元(C)无最大元，有最小元(D)无最大元，无最小元‘01001、101103、图G的邻接矩阵A=0100101001JOI10,(A)无欧拉通路，有哈密顿回路(B)有欧拉回路，无哈密顿通路(C)有欧拉通路，无哈密顿回路(D)无欧拉回路，有哈密顿通路4、设7T是非零实数集，下面关系屮是等价关系的是(C)(A){(兀,刃卜+y>0}(B){(x,y)

8、x+y<0}(C){(x,y)

9、xy>0}5、和谓词公式0x(A(x)tB)等值的是(C)(A)VxA(x)

10、—>B(B)B—>3xA(x)(C)3xA(x)TB(D)BtVxA(x)四、计算题(每题4分，共20分)得分1、化简命题公式-it/—((卩―C])—>—1/7)o解:rqT((pTg)T—1〃)=qv((〃Tq)T—«p)=qv(7ptq)v「p)=qv(~

11、心)}R4=R5=•••=0所以:((心=乙疋=RoR2tR3,n=l={ab),{b.c(b,da0),(⑦c)，(a,d(b,e),(a,e)}3、在复数集C上定义关系R={(a+bi,c^di)h=d},给出这个等价类的儿何说明。解：[a+bi]R={x+bixeR}所以等价类是复平面上平行于实轴的直线。(01001、101104、图G的邻接矩阵A=01001,求从顶点岭到顶点vy长度为3的不同通路的个数。01001J0110丿解：<0600660660宀0600606006(60660丿所以顶点v,到顶点v2长度为

12、3的不同通路的个数是6o5、设集合X={2,346,20}上的关系/?是整除关系，写出偏序关系/?的极人元、极小元。解:偏序关系/?的极大元是6和20；极小元是2和3。五、证明题（每题10分，共20分）图G是简单图，若它的最小度数6（G）>k>lo证明：图G有得分长度为k的革本通路。证明：因为G至少有k条边，所以有基本通路存在。由定理知基本通路的长度不大于ml。设P是所有基本通路中长度最长的一•条，u和v分别是基木通路的起点和终点。若P的长度不小于k,则问题已经解决。若P的长度小于k,因为d（v）>6（G）>k,从顶点v出发至少冇k

13、条边，而基本通路P上异于v的点仅冇k-1个；在图G中还冇另外一个点w和点v相邻接，这样我们得到一条新的基木通路P+{v,w},它比基本通路P还要长，这和P是所有基本通路中长度最长的一条这一事实相矛盾。所以G中最长的基本通路的长度一定不