集合论与图论07答案

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

1、试题：班号：姓名：本试卷满分90分（06级计算机、信息安全专业、实验学院）一、判断对错（本题满分10分，每小题各1分）（正确画“√”，错误画“×”）1．对每个集合，。（×）2．对集合，若，则。（√）3．设若，则。（×）4．设则有。（×）5．若是集合上的等价关系，则也是集合上的等价关系。（√）6．若且是满射，则只要是可数的，那么至多可数的。（√）7．设是有10个顶点的无向图，对于中任意两个不邻接的顶点u和v,均有，则是哈密顿图。（×）8．设是个顶点的无向图的邻接矩阵，则对于的顶点,有成立。（√）9.设是一个图，若，则。（×）10．图和同构当且仅当和的顶点和边分别存在一一对应关系。（×

2、）第6页（共6页）试题：班号：姓名：二.填空(本题40分，每空各2分)1．设则。2．设是任意集合，若，则与关系为。3．设,,则分别为2，3。4．设和是集合且，，若，则从到的单射的个数为。5．设，则从到的满射的个数为。6．设，则。7．设，则。8.设，则。9.设为集合且，则上不同的自反或对称的二元关系的个数为。10．设是的一个划分，则由确定的上的等价关系为。11．，在偏序关系“整除”下的极大元为6，7，8，9，10。12．给出一个初等函数，使得它是从到实数集合的一一对应，这个函数为或-或。13.设是连通图，则的生成树的个数至多为。第6页（共6页）试题：班号：姓名：14．含5个顶点、3条

3、边的不同构的无向图个数为4。15．设无向图有12条边，有6个3度顶点，其余顶点度数均小于3，则中顶点数至少为9。16．由6个顶点，12条边构成的平面连通图中，每个面由3条边围成。17．若为平面图，则的取值为。18．包含完全图作为子图的无向图的顶点色数至少为。19．有向图的可达矩阵中，若,则顶点与之间是互达。20．高为的元正则树至多有片树叶。三、证明和计算（本题40分，每小题各5分）1.设是三个任意集合，证明：。证：设，则，，从而,,。于是，,因此，即。反之，设，有，，从而，，，故且。于是，即。因此，。2.设，。证明：(1)是单射而不是满射；(2)是满射而不是单射；(3)，但；证：（

4、1）若，则，从而，故为单射；但0不存在原象，故不是满射。(2)，,故是满射；但，故不是单射。(3)，故。但，故。第6页（共6页）试题：班号：姓名：3．设是上的一个自反关系，证明：是等价关系若且，则。证：是上的等价关系。若且，由的对称性有：且，由的传递性有：。R是自反的，故有。若，由有，所以是对称的。若且，由的对称性有：且，故由题意得，所以是传递。因此，是上的等价关系。4．设是一个图，证明：是树连通且。证：因为G是树，所以G是连通的；其次对G的顶点数p进行归纳证明p=q+1。当p为1或2时，连通图G中显然有p=q+1。假设对一切少于p个顶点的树结论成立；今设G是有p个顶点树，从G中去

5、掉任一条边x，则G-x恰有两个支。由归纳假设，每个支中顶点数与边数之间有关系式：p1=q1+1，p2=q2+1。所以，p=p1+p2=q1+q2+2=(q1+q2+1)+1=q+1。显然，只须证G中无回路即可。设G中有一个长为n的回路Cn，则回路上有n条边，显然n〈p。于是，G中还有p-n个顶点不在Cn上。由于G是连通的，所以不在Cn上的那些p-n个点的每一个均关联一条边，这些边互不相同，其中每一条都在该点与Cn的某点的最短路上。因此，除了Cn上的n条边之外，G至少还有p-n条边。所以，G至少有q≥p条边，这与p=q+1相矛盾，故G中无回路。5．设是一个无向图，证明:（1）若，则G

6、是连通的；（2）若是连通的，则是否一定有成立？请说明理由。证：(1)因为对的任一对不邻接顶点u和v，有第6页（共6页）试题：班号：姓名：。假设不连通，则至少有两个支。设是其中的一个支，其他各支构成的子图为，其中，，则，有。于是，。矛盾，所以是连通的。(2)这个定理是一个充分条件，不是必要条件,即若是连通的，则不一定成立。例如：6个顶点的一条通路，每个顶点的度，不满足。6．证明：每个自补图必有或个顶点(为正整数)。证：因为每个自补图所对应的完全图的边数必为偶数，即为偶数。而当时，图无自补图，只有时，图才有自补图。于是可写成如下形式：，其中为正整数；代入中，只有才能使q为偶数，故每个自

7、补图必有个顶点。7．设是一棵树且，证明：中至少有个顶点的度为1。证：设中有个顶点，个树叶，则中其余个顶点的度数均大于等于2，且至少有一个顶点的度大于等于。由握手定理可得：，有。所以中至少有个树叶。8．证明：一个没有有向回路（圈）的有向图中至少有一个入度为零的顶点。证：设D=(V,A)是一个没有有向回路的有向图。考察中任一条最长的有向路的第一个顶点v，则id(v)=0。因为若id(v)≠0，则必有一个顶点u使得(u,v)∈A。于是，若u不在此最长路上，则此最长路便不是中