集合论与图论集合论与图论 计算机学院计算机学院 03 年秋季年秋季 （本试题满分 90 分） 一、 （一、 （10 分，每小题分，每小题 1 分）计算：分）计算： 1设 X 和 Y 是集合且Xm=，Yn=。计算从 X 到 Y 的映射的个数。 （答案： ） 2 设 X 和 Y 是集合且Xm=，Yn=。 若 mn， 计算从 X 到 Y 的单射的个数。（答案： ） 3.设 X 为集合且Xn=。计算 X 到 X 的双射的个数。 （答案： ） 4.设 X 为集合且Xn=。计算 X 上有多少个不同的自反的二元关系。 （答案： ） 5.设 X 为集合且Xn=。计算 X 上有多少个二元运算。 （答案： ） 6.设 V12,pu uuL。计算以 V 为顶点集无向图的个数。 （答案： ） 7.设 V12,pu uuL。计算以 V 为顶点集的有向图的个数。 （答案： ） 8.设 V12,pu uuL。计算以 V 为顶点集的比赛图的个数。 （答案： ） 9.（P，P）连通图中有多少个圈？（答案： ） 10. n 个叶子的正则二元树中有多少条有向弧？（答案： ） 二、 （10 分，每小题 1 分）以下每小题中给出了四个答案，其中仅有一个是正确 的。请找出正确的答案并将其号码添在括号中。 二、 （10 分，每小题 1 分）以下每小题中给出了四个答案，其中仅有一个是正确 的。请找出正确的答案并将其号码添在括号中。 11. Km,n 是哈密顿图当且仅当。 （ ） （a）mn （b）mn （c）mn （d） （mn） 12. 下面哪个条件是 Km,n 有哈密顿路的充要条件？（ ） （a）mn （c）mn （d）mn 或 mn+1 13. 设 r2，G 是 r-正则图且1)(=G，则（ ） 14. 把平面分为个区域，使任两个区域相邻，则的最大值为（ ） （a）x(G)r （b）x(G)r （c）x（G）2r （d）x(G)2r （a）5 （b）3 （c）2 （d）4 15. 4 个顶点的二元树（顶点无标号）共有（ ） （a）3 个 （b）4 （c）7 （d）8 16. 设 f：,XY AX，则（ ） （a）1( ( )ff AA （c）-1fAAf)( 1（b）1( ( )ff AA= （d） （a）或（b） 17. :,fXY BY，则（ ） （a）1( )f fBB （c）1( )f fBB （b）1( )f fBB= （d） （b）或（c） 18.设,RXX X为集合。若 R 是偏序关系，则（ ） （a）RR+ （b）RR+= （c）RR+ （d）RR+ 19.下列集合表达式哪一个等于 A（BC）?（ ） I（a） （AB）（AC） （b） （AIB）（AIC） （c） （AB）（AC） UU（d） （AB）U（AC） 20. 置换分解成对换的乘积为（ ） 123456789 791652348 （a） （17） （73） （29） （28） （24） （26） （b） （17） （73） （29） （98） （84） （46） （c） （73） （71） （29） （98） （84） （46） （d） （73） （71） （62） （69） （68） （64） 三、 （10 分） 三、 （10 分） 1. 设 G 是图 1 所示的有向图，写出 G 的邻接矩阵。画出 G 的邻接表表示的示意图。 2. 求到间长为 10 的有向通道的条数的方法是什么？（不必算出具体的数。 ） 1v2v3. 写出 G 的关联矩阵。 4 .画出对应于表达式（AB*C）/（A-C）的二元树表示。 2四、 （10 分，每小题 5 分）证明以下结论： 四、 （10 分，每小题 5 分）证明以下结论： 1.若 G 是一个恰有两个奇度顶点 u 和的图，则 G 是连通的当且仅当 G+uv 是连通的。 2.设 G 是一个（p，q）连通图，则 G 中至少有 q-p+1 个圈。 五、 （15 分，每小题 5 分） 五、 （15 分，每小题 5 分） 1.证明：没有三角形的平面图中必有一个顶点v，deg3。 v 2.应用数学归纳法证明比赛图中必有有向生成路。 3.证明：没有三角形的平面图是 4-可着色的。 3六、 （10 分） 六、 （10 分） 1.给出等价关系、等价类概念的定义。 （4 分） 2.设 D（V,A）是一个有向图。在 V 上定义二元关系：,u uV u当且仅当 u 与互达。证明是等价关系；求的等价类；每个等价类导出的子图是什么子图？ 七、 （7 分）七、 （7 分）设 A，B，C 为集合，试证 A（BC）（AB）（AC） 八、 （8 分）八、 （8 分）给出关系的传递闭包的定义，并根据你的定义证明传递闭包是传递的。 4