《哈工大离散数学dit》由会员分享，可在线阅读，更多相关《哈工大离散数学dit（4页珍藏版）》请在金锄头文库上搜索。
1、应用计算机数学试题A（软件学院DIT）（本考卷满分70分，每题5分）1.设，并设，在A上定义关系为：，证明：（1）是等价关系；（2）计算等价类。证： (1) ，a+b=a+b显示成立，故(a,b)(a,b)R，即R自反；(2) ，若(a,b)，(c,d) R，即R对称的。(3) ，若(a,b)，(c,d) R且且，即是传递的。由(1)、(2)、(3)可知，是上的传递关系。2.设，R是A的幂集上的二元关系且R=(a，b)ab，则R不满足下列哪些性质？为什么？(1)自反性；(2)反自反性；(3)对称性；(4)反对称性；(5)传递性。答：不满足：自反性，反自反性，反对称性，传递性。 满足：对称性3.
2、设 证明：证：=4.设，证明：（1）若与都是可逆的，则也是可逆的;（2）求的逆。证：(1)可逆，故都是一一对应，于是也是一一对应，从而也是可逆的。(2)故。5（1）叙述关系的传递闭包的定义；（2）并给出如下关系的传递闭包。设。答：(1)设是X上的二元关系，所有包含且具有传递关系的交称为关系的传递闭包。(2) +=6.若是一个恰有两个奇度顶点和的图，则连通的是连通的。证：显示成立假设G不连通，则G有K个分支：，由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是，G连通的。7.证明:完全图K9中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路。证：在k9中，故
3、必有一条哈密顿回路；k9去掉C1中所有边后，故也必有一条哈密顿回路；在k9C1中去掉后，,，于是对任一对不相邻顶点u和v，故此时必有一条哈密顿路L。而C1，C2，L彼此无公共边。8.设是一个有个顶点的正则二元树，求的叶子数，其中奇数。解：设T有n个叶子，故有9.设G是一个没有三角形的平面图。证明：G是4可着色的。证：对顶点p进行归纳。当p=1,2,3,4时显示成立。假设当p=k时，G是4-可着色的。当p=k+1时，由于G是一个没有三角形的平面图，故，使得，于是，便是一个具有k个顶点的没有三角形的平面图，从而是4-可着色的。由于，故在G中用不与v相邻接的其它颜色给v着色便得G的一个4-可着色。1
4、0.是否存在每个顶点的度数3且只有7条边的简单平面连通图？请证明。证：假设存在这样的简单平面图，则由，有而由；由；为整数，故，于是与(1)矛盾。11.叙述并证明平面连通图的欧拉公式。欧拉公式：若有p个顶点q条边的平面连通图G有f个面，则。证：对面f的个数进行归纳：当f=1时，G没有内部面，所以G中没有圈，故G是树。因此，故成立。假设对一切有不超过f-1个面的平面连通图欧拉公式成立，往证若G是一个有f个面的连通图时欧拉公式也成立，其中。因为，所以G至少有一个内部面，从而G中有圈，它围成一个内部面。从G中到掉这个圈中任一条边x，则就是一个平面连通图且有个面。于是即，因此在G中欧拉公式成立。12.证
5、明:4阶群（G,*）或者是4阶循环群,或者是klein四元群。证：设G是一个4阶群，则G中元素的阶可知是1，2和4。若G中包含阶为4的元a，则，即G是4阶循环群C4；若G中没有阶为4的元，则除单位元e外，其它元素的阶均为2，即且，于是，即。因为，所以G是可交换群，故G是Klein四元群的K4。13.对于12阶循环群G=(a),则 (1)G有多少个子群?分别写出来。(2)全部生成元是什么?解：（1）6个子群;（2）生成元为有4个;14.设G是群,对于元素有一个有限阶r,k是一个整数,则 (1)为r的倍数. (2) r小于或等于群G中元素个数,即。证：(1) 若k是r的倍数，则，使得，于是，若，则，使得于是有：，因为，是满足的最小正整数，所以。因此，即是的倍数。(2)考察这个元素，它们两两不相同。否则，设，两边同乘，则有。由于，这与的阶为矛盾，又因为是G中的r个不同的元素，所以G中至少有r个元，即。
