haihongyuan.com
海量文库 文档专家
当前位置:首页 >> 数学 >>

《集合论与图论》试题2

《集合论与图论》试题2

试 题: 班号: 姓名: 本试卷满分 90 分 (06 级计算机、信息安全专业、实验学院) 一、判断对错(本题满分 10 分,每小题各 1 分) ( 正确画“√” ,错误画“×” ) 1.对每个集合 A , { A} ? 2 A 。 2.对集合 P, Q ,若 P ? Q ? Q, P ? Q ? ? ,则 P ? ? 。 3.设 f : X ? Y , A ? X , 若 f ( x) ? f ( A) ,则 x ? A 。 4.设 f : X ? Y , B ? Y , 则有 f ( f ?1 ( B)) ? B 。 5.若 R 是集合 X 上的等价关系,则 R 2 也是集合 X 上的等价关系。 (×) (√) (×) (×) (√) 6.若 f : X ? Y 且 f 是满射,则只要 X 是可数的,那么 Y 至多可数的。 (√) 7.设 G 是有 10 个顶点的无向图,对于 G 中任意两个不邻接的顶点 u 和 v, 均有 deg u ? deg v ? 9 ,则 G 是哈密顿图。 (×) 8.设 A ? (aij ) 是 p 个顶点的无向图 G 的邻接矩阵,则对于 G 的顶点 v i , 有 deg vi ? ? aij 成立。 j ?1 p (√) (×) 9. 设 G 是一个 ( p, q) 图,若 q ? p ? 1 ,则 ? (G) ? [2 p / q] 。 10.图 G 和 G1 同构当且仅当 G 和 G1 的顶点和边分别存在一一对应关系。 (×) 二.填空(本题 40 分,每空各 2 分) 1.设 S ? {? ,{?}}, 则 2 S ? {? ,{?}, {{?}}, {? ,{?}}} 。 第 页 (共 6 页) 1 试 题: 班号: 姓名: 2.设 A, B 是任意集合,若 A \ B ? B ,则 A 与 B 关系为 A ? B ? ? 。 3.设 X ? {a, b, c}, Y ? {0,1}, Z ? {2,3}; f : X ? Y , f (a) ? f (b) ? 0, f (c) ? 1 , g : Y ? Z , g (0) ? 2, g (1) ? 3 ,则 g ? f (a),g ? f (c) 分别为 2,3 。 4.设 X 和 Y 是集合且 X ? m , Y ? n ,若 m ? n ,则从 X 到 Y 的单射的 个数为 m Cn m! 。 2n ? 2 5.设 X ? {1,2,?, n}, B ? {1,2} ,则从 X 到 Y 的满射的个数为 。 6.设 X ? {1,2,3,4}, R ? {(1,2), (2,2), (3,4)}, S ? {(2,3), (3,1), (4,2)} ,则 R ? ( S ? R) ? {(1,4), (2,4), (3,2)} 。 。 ?1 2 3 4 5? ? 1 2 3 4 5? ?12345? ? 7. 设 ? 1 ? ? ?3 2 5 1 4? ?, ? 2 ? ? ? 4 3 2 1 5? ? ,则 ? 1? 2 ? ? ? 23541 ? ? ? ? ? ? ? 8. 设 X ? {a, b, c, d}, R ? {(a, b), (b, c), (c, a)} ,则 R ? ? {(a, a), (b, b), (c, c), (a, b), (a, c), (b, c), (b, a), (c, a), (c, b)} 。 9. 设 X 为集合且 X ? n ,则 X 上不同的自反或对称的二元关系的个数 为 2 n2 ? n ?2 n2 ? n 2 ?2 n2 ? n 2 。 10.设 X ? {a, b, c, d}, A ? {{a, b},{c},{d}} 是 X 的一个划分,则由 A 确定的 X 上的等价关系为 {(a, a), (b, b), (a, b), (b, a), (c, c), (d , d )} 。 11. S ? {1,2,?,10} ,在偏序关系“整除”下的极大元为 6,7,8,9,10 。 12.给出一个初等函数 f ( x) ,使得它是从 (0,1) 到实数集合 R 的一一对应, 这个函数为 ct g ?x 或- ctg ?x 或 tg (?x ? ? / 2) 。 p 13. 设 G 是 ( p, p) 连通图,则 G 的生成树的个数至多为 14.含 5 个顶点、3 条边的不同构的无向图个数为 4 。 。 15.设无向图 G 有 12 条边,有 6 个 3 度顶点,其余顶点度数均小于 3,则 G 中 2 第 页 (共 6 页) 试 题: 班号: 姓名: 顶点数至少为 9 。 3 条边围成。 16.由 6 个顶点,12 条边构成的平面连通图 G 中,每个面由 17.若 K p 为平面图,则 p 的取值为 ?4 。 p 18.包含完全图 K p 作为子图的无向图的顶点色数至少为 。 。 19.有向图的可达矩阵 R ? (rij ) 中,若 rij ? r ji ? 1,则顶点 v i 与 v j 之间是 互达 20.高为 h 的 r (r ? 2) 元正则树至多有 rh 片树叶。 三、证明和计算(本题 40 分,每小题各 5 分) 1.设 A, B, C 是三个任意集合,证明: A ? ( B \ C ) ? ( A ? B) \ ( A ? C) 。 证:设 ( x, y) ? A ? ( B \ C ) ,则 x ? A , y ? B \ C ,从而 x ? A , y ? B , y ? C 。 于是 ( x, y) ? A ? B , ( x, y) ? A ? C ,因此 ( x, y) ? ( A ? B) \ ( A ? C) ,即 A ? ( B \ C ) ? ( A ? B) \ ( A ? C ) 。 反之,设 ( x,

网站首页 | 网站地图
All rights reserved Powered by 海文库 haihongyuan.com
文档资料库内容来自网络,如有侵犯请联系客服。3088529994@qq.com