复旦大学计算机科学技术学院 2013-2014第一学期《集合与图论》期末考试试卷 A卷共8页 2014年1月15日 课程代码:COMP120005.01-02 考试形式:闭卷 (本试卷答卷时间为120分钟,答案必须写在试卷上,做在草稿纸上无效) 专业 学号 姓名 成绩 题号 三四|五|六|七|八九|十总分 得分 、判断下列结论是否正确,并说明理由(每题5分,其中判断正误1分,说明理由4分,共30分) ⌒装订线内不要答题 1.有限非空偏序集不一定存在极大元和极小元。 2.设G(V,E)为连通图,T为它的一棵生成树。则G关于T的基本割集的个数等于它的基本回路 的个数 3.设R为非空集合A上的二元关系。则R是传递关系当且仅R2=R。 第1页
第 1 页 （ 装 订 线 内 不 要 答 题 ） 复 旦 大 学 计 算 机 科 学 技 术 学 院 2013-2014 第一学期《集合与图论》期末考试试卷 A 卷 共 8 页 2014 年 1 月 15 日 课程代码：COMP120005.01-02 考试形式：闭卷 （本试卷答卷时间为 120 分钟，答案必须写在试卷上，做在草稿纸上无效） 专业 学号 姓名 成绩 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 一、判断下列结论是否正确, 并说明理由(每题 5 分，其中判断正误 1 分，说明理由 4 分，共 30 分)。 1. 有限非空偏序集不一定存在极大元和极小元。 2. 设 G V E ( , ) 为连通图， T 为它的一棵生成树。则 G 关于 T 的基本割集的个数等于它的基本回路 的个数。 3. 设 R 为非空集合 A 上的二元关系。则 R 是传递关系当且仅 2 R R =
4.如果图G的色数是k,则G至少有k(k-1)/2条边。 5.设N(VEC)为网络,∫为它的一个可行流,(P,P)为它的一个割。如果V=C(PP), 则∫一定为最大流,(P,P)为最小割 ⌒装订线内不要答题 6.设G是n个(n≥1)顶点的简单图。若G不连通,则G的补图G一定是连通的 第2页
第 2 页 （ 装 订 线 内 不 要 答 题 ） 4. 如果图 G 的色数是 k ，则 G 至少有 k k( 1) / 2 − 条边。 5. 设 N V E C s t ( , , , , ) 为网络， f 为它的一个可行流， ( , ) P P 为它的一个割。如果 ( , ) V C P P f = ， 则 f 一定为最大流， ( , ) P P 为最小割。 6. 设 G 是 n 个（ n 1 ）顶点的简单图。若 G 不连通，则 G 的补图 G 一定是连通的
、试求 (1)n本不同的书放入m个不同的盒子中,要求每个盒子至少有一本书,共有多少种不同的放法? (2)n本相同的书放入m个不同的盒子中,要求每个盒子至少有一本书,共有多少种不同的放法? (每小题5分,共10分) ⌒装订线内不要答题 第3页
第 3 页 （ 装 订 线 内 不 要 答 题 ） 二、试求 （1） n 本不同的书放入 m 个不同的盒子中，要求每个盒子至少有一本书，共有多少种不同的放法？ （2） n 本相同的书放入 m 个不同的盒子中，要求每个盒子至少有一本书，共有多少种不同的放法？ （每小题 5 分，共 10 分）
三、设图G的顶点数为n,(O)>0。则a1(G)+月(O)=n,其中a(G)B(G)分别为G的边覆 盖数与边独立数。(12分) ⌒装订线内不要答题 第4页
第 4 页 （ 装 订 线 内 不 要 答 题 ） 三、设图 G 的顶点数为 n， ( ) 0 G 。则 1 1 ( ) ( ) G G n + = ，其中 1 1 ( ), ( ) G G 分别为 G 的边覆 盖数与边独立数。 （12 分）
、求一棵带权为20,2,22…,2的最优12分树,并给出这棵最优12分树的权。(12分) ⌒装订线内不要答题 第5页
第 5 页 （ 装 订 线 内 不 要 答 题 ） 四、求一棵带权为 0 1 2 40 2 ,2 ,2 , ,2 的最优 12 分树，并给出这棵最优 12 分树的权。 （12 分）
五、设A={1234.5},试求可列个A的直积的基数,即求A×A×Ax…。(2分) ⌒装订线内不要答题 第6页
第 6 页 （ 装 订 线 内 不 要 答 题 ） 五、 设 A ={1,2,3,4,5} ，试求可列个 A 的直积的基数，即求 AAA 。 (12 分)
六、若G为3正则简单图,则k(G)=A(G),其中K(G),A(G)分别为G的点连通度和边连通度 (12分) ⌒装订线内不要答题 第7页
第 7 页 （ 装 订 线 内 不 要 答 题 ） 六、若 G 为 3 正则简单图，则 ( ) ( ) G G = ，其中 ( ), ( ) G G 分别为 G 的点连通度和边连通度。 (12 分)
七、设G(X,H)为k-正则的二分图(k>0)。则G一定有一个完美的匹配。(12分) ⌒装订线内不要答题 第8页
第 8 页 （ 装 订 线 内 不 要 答 题 ） 七、设 G X Y ( , ) 为 k − 正则的二分图（ k 0 ）。则 G 一定有一个完美的匹配。 （12 分）