复旦大学计算机科学技术学院 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 分） 证明：
七、某一个市镇只有一家旅馆,这个旅馆与通常旅馆没有不同,只是房间数不是有限 而是无穷多间,房间号码为1,2,3,4,……我们不妨管它叫希尔伯特旅馆。这个 旅馆的房间可排成一列的无穷集合(1,2,3,4,…),称为可列集。 有一天,所有房间都住满了。后来来了一位客人,坚持要住房间。旅馆老板于 是引用“旅馆公理”说:“满了就是满了,非常对不起!”。正好这时候,聪明的旅馆 老板的女儿来了,她看见客人和她爸爸都很着急,就说:“这好办,请每位顾客都搬 下,从这间房搬到下一间”。于是1号房间的客人搬到2号房间,2号房间的客人 搬到3号房间……依此类推。最后1号房间空出来,请这位迟到的客人住下了。 第二天,希尔伯特旅馆又来了一个庞大的代表团要求住旅馆,他们声称有可数 无穷多位代表一定要住,这又把旅馆经理难住了。老板的女儿再一次来解围,她说: “您让1号房间客人搬到2号,2号房间客人搬到4号……,k号房间客人搬到2l 号,这样,1号,3号,5号,……房间就都空出来了,代表团的代表都能住下了 第三天,这个代表团每位代表又出新花招,他们想每个人占可数无穷多间房来 安排他们的亲戚朋友,这回不仅把老板难住了,连老板的女儿也被难住了。 (1)现在您担任希尔伯特旅馆的客房经理,您准备采取什么方法解决当前的住宿问 (2)后来老板的女儿进了大学数学系。有一天,康托尔教授来上课,他问老板的女儿: “要是区间[0,1上每一点都占一个房间,是不是还能安排?”也请您回答康托 尔教授的这一问题,并论证。 (16分,第1小题6分,第2小题10分,其中论证为8分) 第6页
第 6 页 七、某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是有限 而是无穷多间，房间号码为 1，2，3，4，……我们不妨管它叫希尔伯特旅馆。这个 旅馆的房间可排成一列的无穷集合(1，2，3，4，…)，称为可列集。 有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老板于 是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这时候，聪明的旅馆 老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请每位顾客都搬 一下，从这间房搬到下一间”。于是 1 号房间的客人搬到 2 号房间，2 号房间的客人 搬到 3 号房间……依此类推。最后 1 号房间空出来，请这位迟到的客人住下了。 第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有可数 无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解围，她说： “您让 1 号房间客人搬到 2 号，2 号房间客人搬到 4 号……，k 号房间客人搬到 2k 号，这样，1 号，3 号，5 号，……房间就都空出来了，代表团的代表都能住下了。” 第三天，这个代表团每位代表又出新花招，他们想每个人占可数无穷多间房来 安排他们的亲戚朋友，这回不仅把老板难住了，连老板的女儿也被难住了。 (1) 现在您担任希尔伯特旅馆的客房经理，您准备采取什么方法解决当前的住宿问 题？ (2) 后来老板的女儿进了大学数学系。有一天，康托尔教授来上课，他问老板的女儿： “要是区间[0，1]上每一点都占一个房间，是不是还能安排？”也请您回答康托 尔教授的这一问题，并论证。 （16 分，第 1 小题 6 分，第 2 小题 10 分，其中论证为 8 分）
八、设R1和R2是A上的等价关系,C1和C2分别是A中关于R1和R2的划分。(10 分) 线 证明:R1cR2,当且仅当C1中的每个等价类是包含于C2的一些等价类之中。 内 证明 不要答题 第7页
第 7 页 （ 装 订 线 内 不 要 答 题 ） 八、设 R1 和 R2 是 A 上的等价关系，C1和 C2分别是 A 中关于 R1和 R2的划分。（10 分） 证明： R1R2，当且仅当 C1 中的每个等价类是包含于 C2的一些等价类之中。 证明：