计算机学院03年秋季
（本试题满分90分）
一、（10分，每小题1分）计算：
1．设X和Y是集合且X=m，Y=n。计算从X到Y的映射的个数。（答案： ） 2．设X和Y是集合且X=m，Y=n。若m≤n，计算从X到Y的单射的个数。（答案： ） 3.设X为集合且X=n。计算X到X的双射的个数。（答案： ）
4.设X为集合且X=n。计算X上有多少个不同的自反的二元关系。（答案： ） 5.设X为集合且X=n。计算X上有多少个二元运算。（答案： ） （答案： ） 6.设V＝u1,u2Lup。计算以V为顶点集无向图的个数。
7.设V＝u1,u2Lup。计算以V为顶点集的有向图的个数。（答案： ） 8.设V＝u1,u2Lup。计算以V为顶点集的比赛图的个数。（答案： ） 9.（P，P）连通图中有多少个圈？（答案： ）
10. n个叶子的正则二元树中有多少条有向弧？（答案： ）
{{{}}} 二、（10分，每小题1分）以下每小题中给出了四个答案，其中仅有一个是正确的。请找出正确的答案并将其号码添在括号中。
11. Km,n是哈密顿图当且仅当。（ ） （a）m≤n （b）m≥n （c）m＝n 12. 下面哪个条件是Km,n有哈密顿路的充要条件？（ ） （a）m （b）x(G) （d）（m rr 〕 （d）x(G)＝〔〕 22 14. 把平面分为α个区域，使任两个区域相邻，则α的最大值为（ ） （a）5 （b）3 （c）2 （d）4 15. 4个顶点的二元树（顶点无标号）共有（ ） （a）3个 （b）4 （c）7 （d）8 16. 设f：X→Y,A⊆X，则（ ） （a）f −1 (f(A))⊆A （c）f -1 (f(A))⊇A 1 （b）f −1 (f(A))=A （d）（a）或（b） 17. f:X→Y,B⊆Y，则（ ） （a）f(f（b）f(f −1 (B))⊇B (B))=B （c）f(f −1 (B))⊆B −1 （d）（b）或（c） 18.设R⊆X×X,X为集合。若R是偏序关系，则（ ） （a）R⊂R + （b）R=R + （c）R≠R + （d）R⊂R + 19.下列集合表达式哪一个等于A＼（BIC）?（ ） （b）（AIB）\\（AIC） （a）（A\\B）∩（A\\C） （c）（AUB）\\（AUC） （d）（A\\B）U（A\\C） ⎛123456789⎞ 20. 置换⎜⎟分解成对换的乘积为（ ） 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分） 1. 设G是图1所示的有向图，写出G的邻接矩阵。画出G的邻接表表示的示意图。 2. 求v1到v2间长为10的有向通道的条数的方法是什么？（不必算出具体的数。） 3. 写出G的关联矩阵。 4 .画出对应于表达式（A＋B*C）/（A-C）的二元树表示。 2 四、（10分，每小题5分）证明以下结论： 1.若G是一个恰有两个奇度顶点u和υ的图，则G是连通的当且仅当G+uv是连通的。 2.设G是一个（p，q）连通图，则G中至少有q-p+1个圈。 五、（15分，每小题5分） 1.证明：没有三角形的平面图中必有一个顶点v，degv≤3。 2.应用数学归纳法证明比赛图中必有有向生成路。 3.证明：没有三角形的平面图是4-可着色的。 3 六、（10分） 1.给出等价关系、等价类概念的定义。（4分） 2.设D＝（V,A）是一个有向图。在V上定义二元关系≌：∀u,u∈V,u≅υ当且仅当u与υ互达。证明≌是等价关系；求≌的等价类；每个等价类导出的子图是什么子图？ 七、（7分）设A，B，C为集合，试证A×（B\\C）＝（A×B）\\（A×C） 八、（8分）给出关系的传递闭包的定义，并根据你的定义证明传递闭包是传递的。 4 因篇幅问题不能全部显示，请点此查看更多更全内容