集合论与图论2010s (2)

《集合论与图论2010s (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本试卷满分90分（计算机科学与技术学院09级各专业）一、填空(本题满分10分，每空各1分)1．设为集合，则成立的充分必要条件是什么？（）2．设，则从到的满射的个数为多少？（）3．在集合上定义的整除关系“

2、”是上的偏序关系，则最大元是什么？（无）4．设，给出上的一个二元关系，使其同时不满足自反性、反自反性、对称性、反对称和传递性的二元关系。（）5．设为一个有限字母表，上所有字（包括空字）之集记为，则是否是可数集？（是）6．含5个顶点、3条边的不同构的无向图个数为多少？（4）7．若是一个连通图，则至少有多少

3、个生成树?（3)8.如图所示图，回答下列问题：（1）图是否是偶图？（不是）（2）图是否是欧拉图？（不是）（3）图的色数为多少？（4）二、简答下列各题（本题满分40分）1.设为任意集合，判断下列等式是否成立？若成立给出证明，若不成立举出反例。（6分）（1）；（2）。解：（1）不成立。例如即可。（2）成立。，有，即。所以，因此，从而。反之，，有。即，从而。因此，＝。2.设是无向图，判断下列命题是否成立？若成立给出证明，若不成立举出反例。（6分）（1）若图是连通图，则的补图也是连通图。（2）若图是不连通图，则

4、的补图是连通图。解：（1）不一定是连通图。（2）一定连通图。因为不连通，故至少有两个分支，一个是，另外一些支构成的子图是。对于中任意两个顶点和：（1）若，则与不在中邻接。由补图的定义可知：与必在中邻接；（2）若，取，则与，与在都不邻接，故与，与在必邻接，于是就是中的一条路。综上可知，对中任两个顶点和之间都有路连接，故是连通的。3．设集合，上的关系定义如下：（6分）。则（1）写出的关系矩阵；（2）验证是偏序集；（3）画出图。cebad解：（1）所对应的关系矩阵为为：（2）由关系矩阵可知：对角线上的所有元素

5、全为1，故是自反的；，故是反对称的；对应的关系矩阵为：。因此是传递的。综上可知：故是上的偏序关系，从而是偏序集。（3）对应的图如图所示。4．设是有限集合，。则（3分）（1）若是单射，则必是满射吗？反之如何？（2）若是无限集合，结论又如何？解：（1）是单射，则必是满射；反之也成立；（2）若是无限集合，结论不成立。举例：令N＝{1，2，3，…｝，则（1）设，。显然，Ｓ是单射，但不是满射。（2）设，。显然，是满射，但不是单射。5．（4分）（1）根据你的理解给出关系的传递闭包的定义；（2）设，上的关系，求关系的

6、传递闭包。解：（1）设是集合上的二元关系，则上包含的所有传递关系的交称为关系的传递闭包。（2）6．由6个顶点，12条边构成的平面连通图中，每个面由几条边围成？说明理由。（4分）解：每个面由3条边围成。在图中，，，根据欧拉公式，得。因为简单平面连通图的每个面至少由3条边围成，所以假设存在某个面由大于3条边围成，则有：，即，矛盾。故每个面至多由3条面围成，于是中每个面由3条边围成的。7．设是至少有一个顶点不是孤立点的图。若为偶数，则中是否必有圈？说明理由。（4分）解:中必有圈。令是中的一条最长的路，，则由知

7、，必有某个顶点与邻接。由于是最长路，所以必是中的某个。于是，是的一个回路。8．设是一个有个叶子的二元树，出度为2的顶点为，则与有何关系？说明理由。（4分）解：与的关系为：由且，得，得。9．已知有向图的邻接矩阵，则（3分）（1）画出邻接矩阵为的有向图的图解；（2）写出的可达矩阵；（3）写出计算两顶点之间长为的有向通道条数的计算方法。解：（1）（2）；（3）。三、证明下列各题（本题满分40分，每小题各5分）1．设是一个图，证明：是树无圈且。证：因为G是树，所以G是无圈；其次对G的顶点数p进行归纳证明p=q+

8、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．设，证明：是单

9、射。证：（1），则，于是中必存在，使得。因为是单射，故必有。即，所以。反过来，，从而有，所以。因此。假设不是单射，则，但。令，于是，故有，矛盾。即一定为单射。3．设是一个个顶点的图。和是的两个不邻接的顶点，并且。证明：是哈密顿图是哈密顿图。证明：显然成立。假设G不是哈密顿图，则有题意知在G中必有一条从u到v的哈密顿路。不妨设此路为,令degv1=k，degvp=l,则在G中与u邻接的顶点为ui1，ui2，…，uik，其中2=i1