哈工大离散数学dit05.docVIP

应用计算机数学试题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 ︱a∩b≠￠ ，则R不满足下列哪些性质？为什么？ 1 自反性； 2 反自反性； 3 对称性； 4 反对称性； 5 传递性。 答：不满足：自反性，反自反性，反对称性，传递性。 满足：对称性 3.设 证明： 证： 4.设，证明： （1）若与都是可逆的，则也是可逆的; （2）求的逆。 证： 1 可逆，故都是一一对应，于是也是一一对应，从而也是可逆的。 2 故。 5（1）叙述关系的传递闭包的定义；（2）并给出如下关系的传递闭包。 设。 答： 1 设是X上的二元关系，所有包含且具有传递关系的交称为关系的传递闭包。 2 + 6.若是一个恰有两个奇度顶点和的图，则连通的是连通的。 证：显示成立 假设G不连通，则G有K个分支：，由题意不在一个分支上，于是含有的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是，G连通的。 7.证明:完全图K9中至少存在彼此无公共边的两条哈密顿回路和一条哈密顿路。 证：在k9中，故必有一条哈密顿回路；k9去掉C1中所有边后，，故也必有一条哈密顿回路；在k9\C1中去掉后，,，于是对任一对不相邻顶点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-可着色。 10.是否存在每个顶点的度数≥3且只有7条边的简单平面连通图？请证明。 证：假设存在这样的简单平面图，则由，有 而由；由；为整数，故，于是与 1 矛盾。 11.叙述并证明平面连通图的欧拉公式。 欧拉公式：若有p个顶点q条边的平面连通图G有f个面，则。 证：对面f的个数进行归纳：当f 1时，G没有内部面，所以G中没有圈，故G是树。因此，故成立。 假设对一切有不超过f-1个面的平面连通图欧拉公式成立，往证若G是一个有f个面的连通图时欧拉公式也成立，其中。因为，所以G至少有一个内部面，从而G中有圈，它围成一个内部面。从G中到掉这个圈中任一条边x，则就是一个平面连通图且有个面。于是即，因此在G中欧拉公式成立。 12.证明:4阶群（G,*）,或者是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个元，即。