复旦大学计算机科学技术学院 《集合与图论》期末考试试卷 A卷共8页 013年1月16日 课程代码:INF012000801-02 考试形式:闭卷 (本试卷答卷时间为120分钟,答案必须写在试卷上,做在草稿纸上无效) 专业 学号 姓名 成绩 题号 三三|四|五六七|八九十总分 得分 、判断下列结论是否正确,并说明理由(每题5分,其中判断正误1分,说明理由4分,共20分) 线 1.割集一定是断集,断集不一定是割集。 内不要答题 2.设G1G2为平面图。若G1=G2,则G≡G2,其中G,G2分别为G1,G2的对偶。 3.设A={1,2,3,4,5},R={(1,2)},则R为A上的传递关系。 第1页
第 1 页 （ 装 订 线 内 不 要 答 题 ） 复 旦 大 学 计 算 机 科 学 技 术 学 院 《集合与图论》期末考试试卷 A 卷 共 8 页 2013 年 1 月 16 日 课程代码：INF0120008.01-02 考试形式：闭卷 （本试卷答卷时间为 120 分钟，答案必须写在试卷上，做在草稿纸上无效） 专业 学号 姓名 成绩 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 一、判断下列结论是否正确, 并说明理由(每题 5 分，其中判断正误 1 分，说明理由 4 分，共 20 分)。 1. 割集一定是断集，断集不一定是割集。 2. 设 1 2 G G, 为平面图。若 G G 1 2 ，则 * * G G 1 2 ，其中 * * 1 2 G G, 分别为 1 2 G G, 的对偶。 3. 设 A R = = {1,2,3,4,5}, {(1,2)} ，则 R 为 A 上的传递关系
4.(6,6,5,4,3,3,2,2,2,1)是一个简单图的度序列 、求带权为1,2,3,4,5,6,78,9,10,11的最优4分树,并计算出它的权。(10分) ⌒装订线内不要答题 第2页
第 2 页 （ 装 订 线 内 不 要 答 题 ） 4. (6,6,5,4,3,3,2,2,2,1) 是一个简单图的度序列。 二、求带权为 1,2,3,4,5,6,7,8,9,10,11 的最优 4 分树，并计算出它的权。 （10 分）
三、证明:强连通的竞赛图一定是 Hamilton图(12分) ⌒装订线内不要答题 第3页
第 3 页 （ 装 订 线 内 不 要 答 题 ） 三、证明：强连通的竞赛图一定是 Hamilton 图（12 分）
四、现有5位教师T1,T2,T3,T4,T要给7个班级C1,C2,C3C,C,C6,C7上课,教学任务如下表: C6 TTTTT C22 C02301 30002 G0204 G00 103 321 上表中T所在的行与C所在的列的交叉位置的数字表示教师T为班级C所上的课时数。现在教务员 要上面的教学任务安排课程表,要求在同一课时里,一位教师只能给一个班级上课,同一个班级也只 能有一位教师上课。为完成上述教学任务,至少要安排多少个课时?如果教务员只有4个教室可使用, 那么为完成上述教学任务,至少要安排多少个课时?(12分)。 ⌒装订线内不要答题 第4页
第 4 页 （ 装 订 线 内 不 要 答 题 ） 四、现有 5 位教师 T1,T2,T3,T4,T5 要给 7 个班级 C1,C2,C3,C4,C5,C6 ,C7 上课，教学任务如下表： 班级 教师 C1 C2 C3 C4 C5 C6 C7 T1 2 0 3 1 0 1 0 T2 2 2 0 0 2 1 0 T3 0 3 0 1 0 3 2 T4 1 0 0 0 4 2 1 T5 1 1 2 3 0 1 2 上表中 Ti 所在的行与 Cj 所在的列的交叉位置的数字表示教师 Ti 为班级 Cj 所上的课时数。现在教务员 要上面的教学任务安排课程表，要求在同一课时里，一位教师只能给一个班级上课，同一个班级也只 能有一位教师上课。为完成上述教学任务，至少要安排多少个课时？如果教务员只有 4 个教室可使用， 那么为完成上述教学任务，至少要安排多少个课时？（12 分）
五、复旦计算中心安排5名青年教师ⅹ,¤,x,Ⅺ,ⅹ值夜班,从周一到周五每个青年教师值一晩。 其中x1不安排在周一值班,x不安排在周二值班,x不安排在周三值班。问:共有多少种不同的安 排值班方法?(10分) ⌒装订线内不要答题 第5页
第 5 页 （ 装 订 线 内 不 要 答 题 ） 五、复旦计算中心安排 5 名青年教师 x1，x2，x3，x4，x5 值夜班，从周一到周五每个青年教师值一晚。 其中 x1 不安排在周一值班，x2 不安排在周二值班，x3 不安排在周三值班。问：共有多少种不同的安 排值班方法？ (10 分)