离散数学期末试题seu

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,离散数学,-,期末例题,仅供参考，不代表最后试题,2,1.,求下图中,v,0,与,v,5,的最短路径,3,v,i,r,v,0,v,1,v,2,v,3,v,4,v,5,0,2,1,1,2,4,2,2,4,2,7,3,4,7,4,6,5,W,0,2,1,4,2,6,所以,v,0,与,v,5,的最短路径为,v,0,v,2,v,3,v,5,，长度为,6,。,解：,4,2.,有向图,D,如图所示,D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各为几条？,D,中,v,1,到,v,1,长度为,1,2,3,4,的回路各为几条？,D,中长度为,4,的通路有多少条？其中长为,4,的回路有多少条？,D,中长度小于或等于,4,的通路有多少条？其中有多少条为回路？,5,图,D,的邻接矩阵为,解：,则,D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各为,0,0,2,2,条,D,中,v,1,到,v,1,长度为,1,2,3,4,的通路各为,1,1,3,5,条,D,中长度为,4,的通路有,44,条，其中长为,4,的回路有,11,条,(4),D,中长度小于或等于,4,的通路有,88,条，其中有,22,条为回路,6,3.,求公式的主析取范式、主合取范式、成真赋值和成假赋值,解：,(,p,q,),r,(,p,q,),r,(,p,q,),r,(,p,q,(,r,r,),),(,p,p,)(,q,q,),r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),m,0,m,1,m,3,m,5,m,7,（主析取范式）,主合取范式为,(,p,q,),r,M,2,M,4,M,6,成真赋值为,000,001,011,101,111,成假赋值为,010,100,110,7,4.,A,=1,2,12,为整除关系，画出,(,A,),的哈斯图，并求,B,=2,3,6,的极大元、极小元、最大元、最小元、上界、下界、最小上界和最大下界,解：,B,=2,3,6,的,极大元,6,极小元 无,最大元,6,最小元 无,上界,6,12,下界,1,最小上界,6,最大下界,1,8,5.,给出,A,=1,2,3,上所有的等价关系,解：,A,上的划分共有,5,种,1,2,和,3,分别对应等价关系,R,1,R,2,和,R,3,.,R,1,=,I,A,，,R,2,=,I,A,R,3,=,I,A,4,对应于全域关系,E,A,，,5,对应于恒等关系,I,A,9,6.,设集合,X,=1,2,3,4,，定义在,X,上的二元关系为,R,=,S,=,计算,R,S,和,S,R,，说明,R,的性质。,解：,R,S,=,S,R,=,求关系合成的三种计算方法：,集合表示法,图示法,关系矩阵,R,是非自反的、非反自反的、非对称的、反对称的、传递的,