哈工大03年集合与图论试题与答案.pdf

《集合论与图论》 计算机学院 03 年秋季 参考答案 一、（10 分，每小题 1 分）计算： 1．设X 和 Y 是集合且 X m ， Y n 。试计算从X 到 Y 的映射的个数。（答案：nm ） 2 ．设X 和 Y 是集合且 X m ，Y n 。若m ≤n，试计算从 X 到Y 的单射的个数。（答案： Cm m ! pm n n ） 3.设X 为集合且 X n 。计算 X 到X 的双射的个数。（答案：n！） 2 n n − 4.设X 为集合且 X n 。计算 X 上有多少个不同的自反的二元关系。（答案：2 ） 2 5.设X 为集合且 X n 。计算 X 上有多少个二元运算。（答案：nn ） n (n−1) 6.设V＝{u ,u Lu }。计算以 V 为顶点集无向图的个数。（答案：2 2 ） 1 2 p n(n-1) 7.设V＝{u ,u Lu }。计算以V为顶点集的有向图的个数。（答案：2 ） 1 2 p n (n−1) 8.设V＝{u ,u Lu }。计算以 V 为顶点集的比赛图的个数。（答案：2 2 ） 1 2 p 9.（P，P）连通图中有多少个圈？（答案：1） 10. n 个叶子的正则二元树中有多少条有向弧？（答案：2（P-1）） 二、（10分，每小题 1分）以下每小题中给出了四个答案，其中仅有一个是正确 的。请找出正确的答案并将其号码添在括号中。 11.Km,n 是哈密顿图当且仅当。（c） （a）m≤n （b）m≥n （c）m＝n （d）（mn或 mn） 12.下面哪个条件是 Km,n有哈密顿路的充要条件？（d） （a）mn （b）mn （c）m＝n （d）m＝n或 m＝n+1 13.设 r≥2，G 是r-正则图且 ，则（c） ( ) χ1G （a）x(G)＝r （b）x(G)r r r （c）x（G）≤〔 〕 （d）x(G)＝〔 〕 2