则 R= 。 60. 设

A?{a,b,c,d,e,f},R?IA{?a,b?,?b,a?,?e,f?,?f,e?,

?a,e?,?e,a?,?a,f?,?f,a?,?b,f?,?f,b?,?b,e?,?e,b?},且R是A上

的等价关系,则61. 设

AR= 。

A?{a,b,c,d,e,f},R?IA{?a,b?,?b,a?,?e,f?,?f,e?,

?a,e?,?e,a?,?a,f?,?f,a?,?b,f?,?f,b?,?b,e?,?e,b?},且R是A上

的等价关系,则

?a?R? 。

62. (1) 已知 A={1，2，3，4，5}上的等价关系R，

R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,5>,<5,3>,<5,5>,<4,4>} 写出R对应的划分。

(2) 已知 A={1，2，3，4，5}上的一个划分D={{1，3}，{2}，{4}，{5}} 写出对应的等价关系S。

63. 设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的二元关系。 64. 设A=?a,b,c?, R=

?a,a,a,b,b,b,b,a,b,c,c.c,c,a?，则R具有（ ）

。

001?000??101??000?，

A、 自反性 B、 传递性 C、 对称性 D、 反对称性

?1?1??0?165. 设S={1，2，3，4}，R为S上的关系，其关系矩阵是?求(1) R的关系表达式（用列举法写出）；R的关系图。 (2) R，R。 (3) r(R), s(R)，t(R)。

c

2第三部分：图论

1、非负整数列

d1,d2,,dn是可图化的当且仅当

2、下列非负整数列（ ）是可简单图化的？

A.5,5,4,4,2,1 B.5,4,3,2,2 C.3,3,3,1 D.4,4,3,3,2,2

3、无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶

13

数n为几？

4、已知无向图G中顶点数n与边数m相等，2度与3度顶点各2个，其余顶点均为悬挂顶点，试求G的边数m。 5、设

d1,d2,,dn为n个互不相等的正整数，证明

d1,d2,,dn不可简单图化。

6、下图的点连通度是 ，边连通度是 。

7写出下图中所有的点割集

8、下面无向图的点连通度是 ，边连通度是。

9 下面有向图中有 个是强连通的？

10、写出下面无向图的关联矩阵 。

11、写出下面有向图的关联矩阵 。

14

12、写出下列有向图的邻接矩阵

13、写出下面有向图的可达矩阵

14、设图G的邻接矩阵为

??00100??00011???10000???01001??

??01010??

则G的边数为( )．

A．5 B．6 C．3 D．4

15、已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边 16、下列（ ）是欧拉图。

。

15

17 下图中,（ ）是欧拉图。

A B C D 18、完全图

Kn(n?3)，当n为 时，

Kn是欧拉图。

19、命题“n(n?2)阶有向完全图是欧拉图”的真值是 。 20、命题“当r,s为正偶数时，完全二部图Kr,s是欧拉图”的真值是 。

21、在完全图

K2k(k?2)上至少加 条边，才能使所得图为欧拉图。22、判断下列图是哈密顿图、半哈密顿图、还是都不是？

23 下图中既是欧拉图又是哈密顿图的是（ ） A．

K9 B．

K10 C．

K2,3 D．

K3,3

24、设完全二部图

Kr,s为哈密顿图，则r,s应满足 。

25 说明图 G （如图5所示）不是汉密尔顿图．

16