复旦大学计算机科学技术学院 《集合与图论》期末考试试卷 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 分)
六、由0,1,23,4,5组成的n位数中,要求0出现至多一次,1出现奇数次,2出现偶数次,3,4,5出现 的次数没有限制,求这样的n位共有多少个?(10分) ⌒装订线内不要答题 第6页
第 6 页 （ 装 订 线 内 不 要 答 题 ） 六、由 0,1,2,3,4,5 组成的 n 位数中，要求 0 出现至多一次，1 出现奇数次，2 出现偶数次，3,4,5 出现 的次数没有限制，求这样的 n 位共有多少个？ (10 分)
七、求可列个可列集的直积的阶。(12分) ⌒装订线内不要答题 第7页
第 7 页 （ 装 订 线 内 不 要 答 题 ） 七、求可列个可列集的直积的阶。 （12 分）
八、设N(V,E,c,S,1)为一个网络,∫是它的一个可行流。试证明 (1)若P是∫的可增路,即P是s到t的路,且Ⅳ(P)>0,其中l(P)= min{l(a)}, c(a)-f(a),当a是P的同向弧 l(a) /(a)当a是P的反向弧 。现在网络N上定义新的流∫如下 f(a)+l(P),当a是P的同向弧, f(a)={f(a)-1(P),当a是P的反向弧, f(a 其它 则∫是一定是N的可行流,且V=V+l(P) (2)∫是N最大流当且仅当N没有∫可增路。(共14分,每小题7分) ⌒装订线内不要答题 第8页
第 8 页 （ 装 订 线 内 不 要 答 题 ） 八、设 N V E c s t ( , , , , ) 为一个网络， f 是它的一个可行流。试证明： （1）若 P 是 f 的可增路，即 P 是 s 到 t 的路，且 l P( ) 0 ，其中 ( ) min { ( )} a P l P l a = ， ( ) ( ), ( ) ( ), c a f a a l a f a a − = 当 是P的同向弧 当 是P的反向弧 。现在网络 N 上定义新的流 f 如下： ( ) ( ), ( ) ( ) ( ), ( ), f a l P a f a f a l P a f a + = − 当 是P的同向弧, 当 是P的反向弧, 其它. 则 f 是一定是 N 的可行流，且 ( ) f f V V l P = + 。 （2） f 是 N 最大流当且仅当 N 没有 f 可增路。 （共 14 分，每小题 7 分）