精选优质文档-----倾情为你奉上本试卷满分90分（计算机科学与技术学院09级各专业）一、填空(本题满分10分，每空各1分)1．设为集合，则成立的充分必要条件是什么？（）2．设，则从到的满射的个数为多少？（ ）3．在集合上定义的整除关系“|”是上的偏序关系， 则最大元是什么？ （ 无 ）4．设，给出上的一个二元关系，使其同时不满足自反性、反自反性、对称性、反对称和传递性的二元关系5．设为一个有限字母表，上所有字（包括空字）之集记为，则是 否是可数集？ （ 是 ）6．含5个顶点、3条边的不同构的无向图个数为多少？ （ 4 ）7．若是一个连通图，则至少有多少个生成树? （ 3 )8. 如图所示图，回答下列问题： （1）图是否是偶图？ （ 不是 ）（2）图是否是欧拉图？ （ 不是 ）（3）图的色数为多少？ （ 4 ） 二、简答下列各题（本题满分40分）1.设为任意集合，判断下列等式是否成立？若成立给出证明，若不成立举出反例。
6分）（1）；（2）解：（1）不成立例如即可 （2）成立所以，因此，从而反之，，有即，从而因此，＝2. 设是无向图，判断下列命题是否成立？若成立给出证明，若不成立举出反例6分）（1）若图是连通图，则的补图也是连通图2）若图是不连通图，则的补图是连通图解：（1）不一定是连通图 （2）一定连通图因为不连通，故至少有两个分支，一个是，另外一些支构成的子图是对于中任意两个顶点和：（1）若，则与不在中邻接由补图的定义可知：与必在中邻接；（2）若，取，则与，与在都不邻接，故与，与在必邻接，于是就是中的一条路综上可知，对中任两个顶点和之间都有路连接，故是连通的3．设集合，上的关系定义如下：（6分） 则 （1）写出的关系矩阵； （2）验证是偏序集； （3）画出图cebad解：（1）所对应的关系矩阵为为：（2）由关系矩阵可知：对角线上的所有元素全为1，故是自反的；，故是反对称的； 对应的关系矩阵为：因此是传递的综上可知：故是上的偏序关系，从而是偏序集3）对应的图如图所示4．设是有限集合，则（3分）（1）若是单射，则必是满射吗？反之如何？（2）若是无限集合，结论又如何？解：（1）是单射，则必是满射；反之也成立；（2）若是无限集合，结论不成立。
举例：令N＝{1，2，3，…｝，则（1）设，显然，Ｓ是单射，但不是满射2）设，显然，是满射，但不是单射5．（4分）（1）根据你的理解给出关系的传递闭包的定义； （2）设，上的关系，求关系的传递闭包解：（1）设是集合上的二元关系，则上包含的所有传递关系的交称为关系的传递闭包 （2）6．由6个顶点，12条边构成的平面连通图中，每个面由几条边围成？说明理由4分）解：每个面由3条边围成在图中，，，根据欧拉公式，得因为简单平面连通图的每个面至少由3条边围成，所以假设存在某个面由大于3条边围成，则有：，即，矛盾故每个面至多由3条面围成，于是中每个面由3条边围成的7．设是至少有一个顶点不是孤立点的图若为偶数，则中是否必有圈？说明理由4分）解: 中必有圈令是中的一条最长的路，，则由知，必有某个顶点与邻接由于是最长路，所以必是中的某个于是，是的一个回路8．设是一个有个叶子的二元树，出度为2的顶点为，则与有何关系？说明理由4分）解：与的关系为：由且，得，得9．已知有向图的邻接矩阵，则（3分）（1）画出邻接矩阵为的有向图的图解；（2）写出的可达矩阵；（3）写出计算两顶点之间长为的有向通道条数的计算方法。
解： （1） （2） ； （3） 三、证明下列各题（本题满分40分，每小题各5分）1．设是一个图，证明：是树无圈且证：因为G是树，所以G是无圈；其次对G的顶点数p进行归纳证明p=q+1当p为1或2时，连通图G中显然有p=q+1假设对一切少于p个顶点的树结论成立；今设G是有p个顶点树，从G中去掉任一条边x，则G-x恰有两个支由归纳假设，每个支中顶点数与边数之间有关系式：p1=q1+1，p2=q2+1所以，p=p1+p2=q1+q2+2=(q1+q2+1)+1=q+1只须证明G连通即可假设G不连通，则必有k个支且k≥2由于每个支都是连通的且无回路，故每个支都是树于是，对每个支都有由假设k≥2，这与p=q+1相矛盾因此，G是连通的即G是树2．设，证明：是单射证：（1），则，于是中必存在，使得因为是单射，故必有即，所以反过来， ，从而有，所以假设不是单射，则，但令，于是，故有，矛盾即一定为单射3．设是一个个顶点的图和是的两个不邻接的顶点，并且证明：是哈密顿图是哈密顿图证明：显然成立假设G不是哈密顿图，则有题意知在G中必有一条从u到v的哈密顿路。
不妨设此路为,令degv1=k，degvp =l,则在G中与u邻接的顶点为ui1 ，ui2，…，uik，其中2=i1
用对角线法构造一个0，1序列：，则；则一般地，若，则；如果，则，，则确定的函数，但，矛盾所以，不可数7. 设是一个图，若是一个正则偶图，证明：证：因为中无三角形且为正则图，所以，因此，8．设是顶点的平面图，证明：的补图是非平面图证：反证法：假设图的补图也是平面图，令，，则，而 …………. （1）又因为和都是平面图，故，相加得： （2）由（1），（2）的得：，展开有：，于是与题设矛盾，所以不是平面图专心---专注---专业。