离散数学期末试题seu.ppt

《离散数学期末试题seu.ppt》由会员分享，可在线阅读，更多相关《离散数学期末试题seu.ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学离散数学-期末例题期末例题仅供参考，不代表最后试题21.求下图中求下图中v0与与v5的最短路径的最短路径3 virv0v1v2v3v4v502112422 42734 7465W021426所以所以v0与与v5的最短路径为的最短路径为v0v2v3v5，长度为，长度为6。解：解：42.有向图有向图D如图所示如图所示(1)D中中v1到到v4长度为长度为1,2,3,4的的通路各为几条？通路各为几条？(2)D中中v1到到v1长度为长度为1,2,3,4的的回路各为几条？回路各为几条？(3)D中长度为中长度为4的通路有多少的通路有多少条？其中长为条？其中长为4的回路有多的回路有多少条？少条？(4

2、)D中长度小于或等于中长度小于或等于4的通的通路有多少条？其中有多少条路有多少条？其中有多少条为回路？为回路？5图图D的邻接矩阵为的邻接矩阵为 解：解：则则(1)D中中v1到到v4长度为长度为1,2,3,4的通路各为的通路各为0,0,2,2条条(2)D中中v1到到v1长度为长度为1,2,3,4的通路各为的通路各为1,1,3,5条条(3)D中长度为中长度为4的通路有的通路有44条，其中长为条，其中长为4的回路有的回路有11条条(4)D中长度小于或等于中长度小于或等于4的通路有的通路有88条，其中有条，其中有22条为回路条为回路63.求公式的主析取范式、主合取范式、成真赋值和求公式的主析取范式、主

3、合取范式、成真赋值和成假赋值成假赋值解：解：(p q)r(p q)r(pq)r(pq(r r)(p p)(q q)r)(pqr)(pq r)(p q r)(pq r)(p q r)m0 m1 m3 m5 m7（主析取范式）（主析取范式）主合取范式为主合取范式为(p q)rM2 M4 M6成真赋值为成真赋值为000,001,011,101,111成假赋值为成假赋值为010,100,11074.A=1,2,12,为整除关系，画出为整除关系，画出(A,)的哈斯图，的哈斯图，并求并求B=2,3,6的极大元、极小元、最大元、最小元、的极大元、极小元、最大元、最小元、上界、下界、最小上界和最大下界上界、下

4、界、最小上界和最大下界解：解：B=2,3,6的的极大元极大元6极小元极小元无无最大元最大元6最小元最小元无无上界上界6,12下界下界1最小上界最小上界6最大下界最大下界185.给出给出A=1,2,3上所有的等价关系上所有的等价关系解：解：A上的划分共有上的划分共有5种种1,2和和3分别对应等价关系分别对应等价关系R1,R2和和R3.R1=,IA，R2=,IAR3=,IA4对应于全域关系对应于全域关系EA，5对应于恒等关系对应于恒等关系IA96.设集合设集合X=1,2,3,4，定义在，定义在X上的二元关系为上的二元关系为R=,S=,计算计算R S和和S R，说明，说明R的性质。的性质。解：解：R S=,S R=,求关系合成的三种计算方法：求关系合成的三种计算方法：1.集合表示法集合表示法2.图示法图示法3.关系矩阵关系矩阵R是非自反的、非反自反的、非对称的、反对称的、传递的是非自反的、非反自反的、非对称的、反对称的、传递的