复旦大学计算机科学技术学院 2013-2014第一学期《集合与图论》期末考试试卷 B卷共7页 课程代码:COMP12000考试形式:口开卷國闭卷2014年1月 (本试卷答卷时间为120分钟,答案必须写在试卷上,做在草稿纸上无效) 专业 学号 姓名 成绩 十|总分 得分 、判断下列结论是否正确,并说明理由(每题5分,其中判断正误1分,说明理由4分,共 20分) 1.存在7个结点的自补图。 ⌒装订线内不要答题 2.一个有向图D中仅有一个顶点的入度为0,其余顶点的入度均为1,则D是有根 树 第1页
第 1 页 （ 装 订 线 内 不 要 答 题 ） 复旦大学计算机科学技术学院 2013-2014 第一学期《集合与图论》期末考试试卷 B 卷 共 7 页 课程代码：COMP120005 考试形式：□开卷 □√闭卷 2014 年 1月 （本试卷答卷时间为 120 分钟，答案必须写在试卷上，做在草稿纸上无效） 专业 学号 姓名 成绩 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 一、判断下列结论是否正确, 并说明理由(每题 5 分，其中判断正误 1 分，说明理由 4 分，共 20 分)。 1. 存在 7 个结点的自补图。 （ ） 2. 一个有向图 D 中仅有一个顶点的入度为 0，其余顶点的入度均为 1，则 D 是有根 树。 （ ）
3.设A,B,C,D是任意集合;∫是从A到B的双射,g是从C到D的双射。h AxC→B,其中对于任意的{a, CEAXO,h(a,c)=a,g(以成立。则h是双射 4.设A,B是集合,若存在A到B的满射,则B|l 第2页
第 2 页 3. 设 A, B, C, D 是任意集合；f 是从 A 到 B 的双射，g 是从 C 到 D 的双射。h: AC→BD，其中对于任意的(a, c)AC, h((a, c))=(f(a), g(c))成立。则 h 是双射。 （ ） 4．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ ）
二、证明:任何平面图是5-可着色的。(10分) 证明 ⌒装订线内不要答题 如果在一个地图上任何两个地区都相邻,问在该地图上最多有几个地区?(10分) 第3页
第 3 页 （ 装 订 线 内 不 要 答 题 ） 二、证明：任何平面图是 5-可着色的。 （10 分） 证明： 三、如果在一个地图上任何两个地区都相邻，问在该地图上最多有几个地区？（10 分）
四、R是集合A上的等价关系,|=n,|R=s。对于A关于R的商集AR,A/R=r。证 明:rs≌2。(14分) 第4页
第 4 页 四、R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。证 明：rsn 2。（14 分）
五、如果有一群人,其中有k个人彼此认识或者有l个人彼此不认识。我们用r(kD表示这群人至 少是有几个人的人数,称为 Ramsey数。证明:r3.3)=6。(10分) ⌒装订线内不要答题 六、证明:任何一个竞赛图是半哈密顿图。(10分) 证明: 第5页
第 5 页 （ 装 订 线 内 不 要 答 题 ） 五、如果有一群人，其中有 k 个人彼此认识或者有 l 个人彼此不认识。我们用 r(k, l)表示这群人至 少是有几个人的人数，称为 Ramsey 数。证明：r(3, 3)=6。(10 分) 证明： 六、证明：任何一个竞赛图是半哈密顿图。（10 分） 证明：