内容发布更新时间 : 2024/5/17 10:41:41星期一 下面是文章的全部内容请认真阅读。
哈尔滨工业大学（威海）继续教育学院 年 春 季学期
集合与图论本科 试题
考试形式：开卷 答题时间：90 分钟 本卷面成绩站课程成绩 100 %
（所有答案必须写在答题纸上、标清题号）
一、填空题(每空2分，计20分)
1. 集合{0}的所有子集是______________。
2. 设A={1,2,3,{1,2},{3}}，B={2,{1},{2,3}}，则B- A=__________。
3. 有偏序集(N,≤)，即自然数集N上的小于等于关系，N的子集A={2,3,6,8}的下确界和上确界分别是______、_______。
4. 设A={1,2,3,4,5,6}，R={<1,5>,<2,3>,<2,6>,<3,2>,<3,6>,<5,1>, <6,2>,<6,3>}∪IA，则[1]=_____________，[2]=_______________。
5. n个顶点的有向完全图边数是______，每个顶点的度数是_____。
6. 设图G1=
二、简答题(每题 10 分，计 40 分)
1. 设A是一个非空集合，问
(1)A上是否存在一个既是等价关系又是偏序关系的关系？若不存在，请说明理由；若存在，请给出一个实例。
(2) A上是否存在一个既是自反的又是反自反的关系？若不存在，请说明理由；若存在，请给出一个实例。 2. 是否存在每个顶点的度数≥3且只有7条边的简单平面连通图？请说明理由。
3. 某公司来了9名新员工，工作时间不能互相交谈，为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈，于是，每天吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左右邻均与以前的人不同，问这样的安排法能坚持多久？
4. 有向图D如图所示，
(1) 给出D的邻接矩阵A；
(2) D中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？ (3) D中长度小于或等于4的通路为多少条？其中有多少条回路？
1
三、计算题(每题 10 分，计 20 分)
1. 设A＝{a, b, c, d}，R是A上的二元关系，且R＝{
四、证明题(每题 10 分，计 20 分)
1. 设f:X?Y和g:Y?Z是映射， g是单射且f?g是满射，证明：f是满射。
2. 设G=
哈尔滨工业大学（威海）继续教育学院 年 春 季学期
集合论与图论答案
二、简答题(每题 10 分，计 40 分)
1. 答：(1) A上存在一个既是等价关系又是偏序关系的关系。例如恒等关系IA。 (2) A上不存在一个既是自反的又是反自反的关系。
理由如下：若R是A上的一个自反关系，则IA?R，于是IA∩R≠Ф，因此R不是反自反的。 同理可得若R是A上的一个反自反关系，则R不是自反的。
2. 答：不存在每个顶点的度数≥3且只有7条边的简单平面连通图。 理由如下：假设存在这样的简单平面图，则由p?q?f?2，有
p?f?2?q?9而由?degv?2q,3p?2q,p??1?
214q?；
v?V33214由nf?2q,3f?2q,f?q?；p,f为整数，故p,f?4，于是p?f?8与(1)矛盾。
333. 答：平面上9个互不相同的点分别代表9个新员工，两个人能够相邻就连一条边，于是得到了有9个顶
点的完全图K9。问题中的每种做法就是K9的一个哈密顿圈。
由于每次的安排中，每人的左右邻均与以前的人不同，所以我们的问题就是求K9中有多少个两两无公共边的哈密顿圈。
从K9中随意取一条哈密顿圈，将圈中边从图中都去掉。剩余图中各顶点度数为6，还存在哈密顿圈，再选一个圈，然后将圈中边都去掉，这样做下去可得4条哈密顿圈。分别是：1234567891，1357924681，1473825961，1584936271。
因此这种做法只能维持4天。
4. 答：(1) D的邻接矩阵A：
?1?2A???1??1000?010??001??010??1?32A???2??2000?001??010??001??1?43A???3??3000?010??001??010??1?54A???4??4000?001??010??001?(2) D中长度为1的通路为8条，其中有1条是回路。 D中长度为2的通路为11条，其中有3条是回路。
2
D中长度为3的通路为14条，回路为1条。
D中长度为4的通路为17条，回路为3条。
(3) D中长度小于等于4的通路为50条，其中有8条是回路。
三、计算题(每题 10 分，计 20 分)
1. 解：r(R)＝R∪IA＝{
s(R)＝R∪R-1＝{
t(R)＝?Ri＝{
i?142. 解： 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，则
|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由包含排斥原理得
|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C|
所以 |A∩B∩C|＝75－|A∪B∪C|
＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C| ＝75－140＋55＋20＝10
即没有乘坐过其中任何一种的儿童共10人。
四、证明题(每题 10 分，计 20 分)
1. 证明：对?y?Y，由于g是映射，所以存在z?Z，使得g(y)?z。又由于f?g是满射，所以对上述z，存在x?X，使得f?g(x)?z。从而有g(y)?z?f?g(x)?g(f(x))，因为g是单射，所以
f(x)?y。即对?y?Y，存在x?X使得f(x)?y，因此f是满射。
2. 证明：用反证法证明。
若G不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|=n，且G1中的任一个顶点至多只和G1中的顶点相邻，而G2中的任一顶点至多只和G2中的顶点相邻。任取u?V(G1)，v?V(G2)，则d(u)?|V(G1)|-1，d(v)?|V(G2)|-1。
故d(u)+d(v)?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2=n-2 集合与图论本科试题 一、选择题(每小题2分，共20分) 1. 下列选项中错误的是（ ）。 (A)??? (B)??? (C)??{?} (D)??{?} 2. 设A={a,b,c,d}，A上的等价关系R={ 3