离散数学期中测验题

《离散数学期中测验题》由会员分享，可在线阅读，更多相关《离散数学期中测验题（8页珍藏版）》请在金锄头文库上搜索。

1、数学系数学系 0801、0802 离散数学期中测验题离散数学期中测验题及答案及答案 一、填空一、填空 15% （每小题（每小题 3 分）分）1、 设设 A=2，3，4，5，6上的二元关系上的二元关系，|,是质数xyxyxR则则 R= )6 , 5(),5 , 5(),4 , 5(),3 , 5(),2 , 5(),6 , 4(),5 , 4(),6 , 3(),5 , 3(),4 , 3(),3 , 3(),2 , 3(),6 , 2(),5 , 2(),4 , 2(),3 , 2(),2 , 2(R 的关系矩阵的关系矩阵 MR=00000111111100011111111112、 设设 A

2、=1，2，3，则，则 A 上既不是对称的又不是反对称上既不是对称的又不是反对称的关系的关系 R= ；A 上既是对称的又是反上既是对称的又是反)3 , 2(),1 , 2(),2 , 1 (对称的关系对称的关系 R= A 上空关系上空关系 或或 A 上恒等关系上恒等关系 。3、表达式、表达式 的二元树表示为的二元树表示为 )*()*)*(fedcba4、若一棵完全二元（叉）树有、若一棵完全二元（叉）树有 2n-12n-1 个顶点，则它有个顶点，则它有 n 片树叶。片树叶。5 5、设、设 G 是有是有 n 个结点个结点 m 条边的连通平面图，且有条边的连通平面图，且有 k 个个面，则面，则 k 等

3、于等于(m-n+2)m-n+2)二、选择二、选择 20% （每小题（每小题 2 分）分）1、设、设，S 上关系上关系 R 的关系图为的关系图为 3 , 2 , 1 S则则 R 具有（具有（ D ）性质。）性质。A自反性、对称性、传递性；自反性、对称性、传递性； B反自反性、反自反性、反对称性；反对称性；C反自反性、反对称性、传递性；反自反性、反对称性、传递性； D自反性自反性 。2 2、设、设 G G 是一棵树，则是一棵树，则 G G 的生成树有的生成树有( ( B B ) )棵。棵。A.A. 0 0 B.B. 1 1 C.C. 2 2 D.D. 不能确定不能确定3 3、下列哪一种图不一定是树

4、（、下列哪一种图不一定是树（ C C ） 。A.A.无简单回路的连通图无简单回路的连通图 B.B.有有 n n 个顶点个顶点 n-1n-1 条边的连通条边的连通图图 C.C.每对顶点间都有通路的图每对顶点间都有通路的图 D.D.连通但删去一条边便不连连通但删去一条边便不连通的图通的图4 4、下列图中是欧拉图的有、下列图中是欧拉图的有( ( A A ) )。A.A B.D C.A C D.B D5、N 是自然数集，定义是自然数集，定义（即（即 x 除以除以 3 的余数）的余数） ，3mod )()( ,:xxfNNf则则 f 是（是（ D ） 。A、满射不是单射；、满射不是单射；B、单射不是满射

5、；、单射不是满射；C、双射；、双射； D、不是单射也不是满射、不是单射也不是满射三、判断题三、判断题 5%（每小题（每小题 1 分）分）1、 设设 A=a,a，则，则 a P(A) （ 错错 ）2、 空集只是非空集合的子集空集只是非空集合的子集 （ 错错 ）3、一条回路和任何一棵生成树至少有一条公共边。、一条回路和任何一棵生成树至少有一条公共边。 （ 错错 ）4 4、可能有某种关系，既不是自反的，也不是反自反的。、可能有某种关系，既不是自反的，也不是反自反的。 （ 对对 ）5 5、若两图结点数相同，边数相等，度数相同的结点数目相、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构

6、的。等，则两图是同构的。 （ 错错 ）四、解答题四、解答题 40%（每小题（每小题 8 分）分）1 1、设、设 A=1,2,A=1,2,10,10。下列哪个是。下列哪个是 A A 的划分？若是划分，的划分？若是划分，则它们诱导的等价关系是什么？则它们诱导的等价关系是什么？（1 1）B=1,3,6,2,8,10,4,5,7;B=1,3,6,2,8,10,4,5,7;（2 2）C=1,5,7,2,4,8,9,3,5,6,10;C=1,5,7,2,4,8,9,3,5,6,10;（3）D=1,2,7,3,5,10,4,6,8,9解：（1）和（2）都不是 A 的划分。（3）是 A 的划分。其诱导的等价关

7、系是I,。2、设、设 X=1,2,3,4,5，X 上的关系上的关系 R= , , , , ，求，求 R 的传递闭包的传递闭包 t (R)。解：（用矩阵运算求，过程略）t (R)=, ,3、设、设 S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24， “ ”为为 S 上整除关系，上整除关系，问：问：（1）画出偏序集）画出偏序集的的 Hass 图图,S （2）偏序集）偏序集的极小元、最小元、极大元、最大元的极小元、最小元、极大元、最大元,S 是什么是什么?解（1）=,，,SIHass 图为（2）极小元、最小元是 1，极大元、最大元是 24。4、构造一个结点数与边数奇偶性相反的欧拉图。

8、、构造一个结点数与边数奇偶性相反的欧拉图。解：5 5、一次会议有、一次会议有 2020 人参加，其中每个人都在其中有不下人参加，其中每个人都在其中有不下 1010个朋友。这个朋友。这 2020 人围成一圆桌入席。有没有可能使任意相邻人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？而坐的两个人都是朋友？为什么？ 解：可以。将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于 10。即图中任两个不相邻的顶点的度数大于等于 20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿

9、回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。五、证明题五、证明题1、设、设 A 是集合，是集合，R AA，则，则 R 是对称的是对称的RR1。证明：R ，R 是对称的，yRx。即R，故R_1 。从Q而 RR-1。反之R-1,即R 。R 是对称的，yRx。即R， QR_1R。故 R=R-1。x，yA，若R ，即R-1。 R=R-1，R。即QyRx，故 R 是对称的。2、若集合（，）、若集合（，） ， （，）（，） ， （，）（，） ，|,12212211yxyxyxyxR（1）证明）证明 R 是是 X 上的等价关系。上的等价关系。（2）求出）求出 X 关于关于 R 的商集。的商

10、集。1）证明：（1）自反性： yxyxXyx由于,自反RRyxyxL,（2）对称性：XyxXyx2211,时当Ryxyx2211,21121221yxyxyxyx也即即有对称性故RRyxyxL1122,（3）传递性：XyxXyxXyx332211,时且当RyxyxRyxyx33222211, )2() 1 (23321221 yxyxyxyx即23123221)2() 1 (yxyxyxyx即1331yxyx有传递性故RRyxyxL3311,由（1） （2） （3）知：R 是 X 上的先等价关系。2） 、X/R=2 ,1R3、设、设 G=是是 n 个顶点的无向图个顶点的无向图(n2)，若对任意

11、，若对任意 u,vV，有，有 d(u)+d(v) n，则，则 G 是连通图。是连通图。证明： 用反证法证明。若若 G 不不连连通，通，则则它可分成两个独立的子它可分成两个独立的子图图 G和和 G ，其中，其中|V(G )|+|V(G )|=n ，且，且 G 中的任一个中的任一个12121顶顶点至多只和点至多只和 G 中的中的顶顶点点邻邻接，而接，而 G 中的任一中的任一顶顶12点至多只和点至多只和 G 中的中的顶顶点点邻邻接。任取接。任取 u V(G ),21v V(G ),则则 d(u) |V(G )|-1, d(v) |V(G )|-1。 。212故故 d(u)+d(v) (|V(G )|-1)+(|V(G )|-1) |V(G )121|+|V(G )|-22=n-2n， ，这这与已知矛盾。与已知矛盾。故故 G 是是连连通通图图。 。