则 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