中国石油大学大学《离散数学》期末复习题及答案

?1?1?1?1?101100010?0?0?0??

8、设A={1,2,3,4}，R是A的二元关系，定义为：R={<1,1>,<1,2>,<2,1>,<3,2>, <3,1>,<4,3>,<4,2>, <4,1>}，写出A上二元关系R的关系矩阵。 解：R的关系矩阵为：

?1?1?1?1?101100010?0?0?0??

deg(v1)＝3，deg+(v1)＝1，deg-(v1)＝2； deg(v2)＝deg+(v4)＝deg-(v2)＝0； deg(v3)＝3，deg+(v3)＝2，deg-(v3)＝1； deg(v4)＝2，deg+(v4)＝1，deg-(v4)＝1；

9、设有向图G如下所示，求各个结点的出度、入度和度数。

10、设有向图G如下所示，求各个结点的出度、入度和度数。

答：

deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1； deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1； deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3； deg(v4)＝deg+(v4)＝deg-(v4)＝0；

11、设无向图G如下所示，求它的邻接矩阵。

deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；

??0A(G)??1??0?1

101?010?101?? 010??12、求命题公式┐(p∧┐q)的真值表。

p 0 0 1 1 q 0 1 0 1 ┐q 1 0 1 0 p∧┐q 0 0 1 0 ┐ (p∧┐q) 1 1 0 1 13、设<2x+y, 5>=<10, x－3y>，求x，y。 解：由定理列出如下方程组：

?2x?y?10 ??x?3y?5求解得x=5，y=0。

14、R1、R2是从{1, 2, 3, 4, 5}到{2, 4, 6}的关系，若R1＝{<1, 2>, <3, 4>, <5, 6>}，R2={<1, 4>, <2, 6>}，计算domR1，ranR1，fldR1，domR2，ranR2，fldR2。

解：domR1={1, 3, 5}，ranR1={2, 4, 6}，fldR1=dom R1∪ran R1={1, 2, 3, 4, 5, 6}； domR2={1, 2}，ranR2={4, 6}，fldR2=dom R2∪ran R2={1, 2, 4, 6}。

15、例：设A={1, 2, 3, 4, 5}，B={3, 4, 5}, C={1, 2, 3}，A到B的关系R={|x+y=6}，B到C的关系S={|y－z=2}，求R?S。

解：R={<1, 5>, <2, 4>, <3, 3>}, S={<3, 1>, <4, 2>, <5, 3>}，从而R?S={<1, 3>, <2, 2>, <3, 1>} 或者因<1, 5>∈R，<5, 3>∈S，所以<1, 3>∈ R?S；因<2, 4>∈R，<4, 2>∈S，所以<2, 2> ∈R?S；因<3, 3>∈R，<3, 1>∈S，所以<3, 1> ∈R?S；从而R?S={<1, 3>, <2, 2>, <3, 1>} 16、集合A={a, b, c}，B={1, 2, 3, 4, 5}，R是A上的关系，S是A到B的关系。R={, , , , }，S={, , , , }，求R?S，S–?R–

1

1

R?S={, , , , , , } (R?S)={<1, a>, <4, a>, <5, a>, <2, b>, <2, c>, <4, c>, <5, c>}

-1

R={, , , , }， S–={<1, a>, <4, a>, <2, b>, <4, c>, <5, c>}

1

–1

S–?R–1={<1, a>, <2, b>, <2, c>, <4, a>, <4, c>, <5, a>, <5, c>}。

1

17、A＝{1, 2, 3, 4, 5, 6}，D是整除关系，画出哈斯图并求出最小元、最大元、极小元和极大元。 解：

5 1 4 6 2 3 1是A的最小元，没有最大元，1是极小元，4、5、6都是A的极大元。

18、设集合A={a,b,c}，A上的关系R={, , }，求R的自反、对称、传递闭包。 r(R)={,,,,} s(R)={,,,,} t(R)={,,,}

19、求下图中顶点v0与v5之间的最短路径。 v1 1 4 7 5 1 v33 v4 2 v5 6 v0 2 v2 解：如下图所示v0与v5之间的最短路径为：v0, v1, v2, v4 , v3, v5 最短路径值为1+2+1+3+2=9

20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。