哈工大2010年集合论与图论试卷.doc

精品文档本试卷满分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）若是无限集合，结论不成立。举例：令N1，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个支且k2。由于每个支都是连通的且无回路，故每个支都是树。于是，对每个支都有。于是，。由假设k2，这与p=q+1相矛盾。因此，G是连通的。即G是树。2设，证明：是单射。证：（1），则，于是中必存在，使得。因为是单射，故必有。即，所以。反过来， ，从而有，所以。因此。假设不是单射，则，但。令，于是，故有，矛盾。即一定为单射。3设是一个个顶点的图。和是的两个不邻接的顶点，并且。证明：是哈密顿图是哈密顿图。证明：显然成立。假设G不是哈密顿图，则有题意知在G中必有一条从u到v的哈密顿路。不妨设此路为,令degv1=k，degvp =l,则在G中与u邻接的顶点为ui1 ，ui2，uik，其中2=i1i2ikp-1。这时顶点uir-1(r=2，3，k)不能与顶点vp邻接。因为此时G有哈密顿回路uv2vir-1vvp-1viru，因此vp至少与u，v2，vp-1中的k个顶点不邻接。于是，lp-1-k，从而k+1p-1,与题设矛盾，故G是哈密顿图。4设是上的一个二元关系，证明：是对称的。证：，由R的对称性有，即，从而RR-1反之，则。由R的对称性有：，从而R-1R故RR-1，若，由RR-1，得，即，故R是对称的。5设是上的一个二元关系，令，使得且。证明：若是上的等价关系，则也是上的等价关系；证：因为是自反的，所以，有。根据的定义，有，所以是自反的；若，则，使得且。因为是对称的，所以且，根据的定义有，所以是对称的；若，则，使得且。因为是传递的，所以。则，使得且。因为是传递的，所以。根据的定义有。所以是传递的。综上可知：是等价关系。6. 利用康托对角线法证明：若可数，则不可数。证：因为，所以只须证明不可数即可。，0，1的无穷序列。若可数，则的元素可排列成无重复项的无穷序列。每个可表成0，1的无穷序列。用对角线法构造一个0，1序列：，则；则。一般地，若，则；如果，则，则确定的函数，但，矛盾。所以，不可数。7. 设是一个图，若是一个正则偶图，证明：。证：因为中无三角形且为正则图，所以，因此，。8设是顶点的平面图，证明：的补图是非平面图。证：反证法