复旦大学计算机科学技术学院 2013-2014第一学期《集合与图论》期末考试试卷 B卷共7页 课程代码:COMP120005考试形式:口开卷國闭卷2014年1月 (本试卷答卷时间为120分钟,答案必须写在试卷上,做在草稿纸上无效 专业 学号 姓名 成绩 题号 三三|四|五|六|七八|九+|总分 得分 、判断下列结论是否正确,并说明理由(每题5分,其中判断正误1分,说明理由4分,共20 ⌒装订线 存在7个结点的自补图 (否) 内 自补图对应的完全图的边数必须是偶数,而7个结点的完全图的边数为21 不要答题 2.一个有向图D中仅有一个顶点的入度为0,其余顶点的入度均为1,则D是有根树 (否) 一个自环和孤立点 3.设A,B,C,D是任意集合:是从A到B的双射,g是从C到D的双射。h:AXC-BxD, 其中对于任意的a, C)EAXC,h(a,c)=a,g(o)成立。则h是双射。 (真) (1)证明h是满射。 对于任意的(b,d)∈B×D,则b∈B,d∈D,因为f是从A到B的双射,g是从C到D 的双射,所以存在a∈A,c∈C,使得f(a)=b,g(c)=d成立;即存在(a,c)∈A×C,使 得h(a,c))=(f(a),g(c)=(b,d成立。所以h是满射。 (2)证明h是内射。 对于任意的(a,c)∈AxC,(a,c)∈A×C,若h(a,c))-h((a2,c2),所以(f(a) g(c))=(f(a2),g(c2)。所以f(a)=f(a),g(c)=g(c2)。因为f是从A到B的双 射,g是从C到D的双射,所以a=a2,c1=c2。则(a1,c)=(a,c)。所以h是内射。 所以h是双射。 第1页第 1 页 （ 装 订 线 内 不 要 答 题 ） 复旦大学计算机科学技术学院 2013-2014 第一学期《集合与图论》期末考试试卷 B 卷 共 7 页 课程代码：COMP120005 考试形式：□开卷 □√闭卷 2014 年 1月 （本试卷答卷时间为 120 分钟，答案必须写在试卷上，做在草稿纸上无效 专业 学号 姓名 成绩 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 一、判断下列结论是否正确, 并说明理由(每题 5 分，其中判断正误 1 分，说明理由 4 分，共 20 分)。 1. 存在 7 个结点的自补图。 （ 否 ） 自补图对应的完全图的边数必须是偶数，而 7 个结点的完全图的边数为 21。 2. 一个有向图 D 中仅有一个顶点的入度为 0，其余顶点的入度均为 1，则 D 是有根树。 （ 否 ） 一个自环和孤立点 3. 设 A, B, C, D 是任意集合；f 是从 A 到 B 的双射，g 是从 C 到 D 的双射。h: AC→BD， 其中对于任意的(a, c)AC, h((a, c))=(f(a), g(c))成立。则 h 是双射。 （ 真 ） （1）证明 h 是满射。 对于任意的(b, d)BD, 则 bB, dD, 因为 f 是从 A 到 B 的双射，g 是从 C 到 D 的双射，所以存在 aA, cC, 使得 f(a)= b, g(c)=d 成立；即存在(a, c)AC, 使 得 h((a, c))=(f(a), g(c))= (b, d)成立。所以 h 是满射。 （2）证明 h 是内射。 对于任意的(a1, c1)AC, (a2, c2)AC, 若 h((a1, c1))=h( (a2, c2))，所以(f(a1), g(c1))= (f(a2), g(c2))。所以 f(a1)= f(a2), g(c1)= g(c2)。因为 f 是从 A 到 B 的双 射，g 是从 C 到 D 的双射，所以 a1=a2, c1=c2。则(a1, c1)= (a2, c2)。所以 h 是内射。 所以 h 是双射